Abstract We consider the problem of real-time motion planning that requires evaluating a minimal number of edges on a graph to quickly discover collisionfree paths. Evaluating edges is expensive, both for robots with complex geometries like robot arms, Figure and for robots 7: Visualization first of threethe of thesensing articu arm from the start configuration (pictured) to any of seven Until Alternate now, selector on onethisof thechallenge randomly generate laziness i.e. deferring edge evaluation until absoprojecting onto the space of end-effector position lutely necessary, with the hope that edges turn out This form is derived from simplifying the induced geometto be ric series; notevalid. that if exp(However, wab ) ? Zba , the allva value infinite. One can some also derive have a lotgiven the inverse: of calculate the values Z if an edge were removed. flowing through them, and This incremental formulation of (7) allows for the correlikelihood sponding score p(e) for ofedges neighbouring to be updated efficie ing each iteration of LazySP as the wlazy value for edges chosen leads to ourare for evaluation key insight updated. inste In fact, if t are stored in a square matrix, the update for all pairs afte edgewe weight can consists ofchoose actively change edges a single vector ou tainty about the validity of paths. We 5 Experiments this is equivalent to the Ba We compared the seven edge selectors on three classes of paradigm shortest path problems. ofThedecision average number region of ated by each, as well as timing results from our implementations,However, the 8.DRD problem are shown in Figure In each case, the es chosen torially so that westhard, ? w, sobut thatalso requires all runs produce paths. The experimental results serve primarily to illustrat ofA*allandpossible that the LWA* algorithmsworlds. Weandpr (i.e. Expand work that combines two DRD algorithms,ForDeach are not optimally edge-efficient, but they also expose differences in behavior and prompt future research directions. and B1 I SEC All experiments T , to overcome were conducted using an open-sou plementation. Motion planning results were implemented usingthat OMPLour approach outperforms (S?ucan, Moll, and Kavraki 2012). Random algorithms ongraphs. art partially-connected a spectrum We teste of 1000for mobile randomly-generatedrobots,undirected graphs wi manipulators 100, with each pair of vertices sharing an edge with probabilityhelicopters. 0.05. Edges have an independent 0.5 probability of having infinite weight, else the weight is uniformly distributed on [1, 2]; the estimated weight was unity for all edges. For the WeightSamp selector, we drew 1000 w sam1 ples at each iteration from the above edge weight distribu