16.412/6.834J Cognitive Robotics February 11, 2004 Probabilistic methods for Kinodynamic Path Planning Based On Advanced Lectures by Paul elliott Aisha Walcott Nathan Ickes and Stanislav Funiak Outline Probabilistic roadmaps Planning in the real world Planning amidst moving obstacles RRT-based planners onclusions
Probabilistic Methods for Kinodynamic Path Planning Based On Advanced Lectures by: Paul Elliott, Aisha Walcott, Nathan Ickes and Stanislav Funiak 16.412/6.834J Cognitive Robotics February 11, 2004 Outline Probabilistic roadmaps Planning in the real world Planning amidst moving obstacles RRT-based planners Conclusions
Outline Probabilistic roadmaps Planning in the real world Planning amidst moving obstacles RRT-based planners Conclusions pplicability of lazy prm to Spheres By Paul elliott
Outline Probabilistic roadmaps Planning in the real world Planning amidst moving obstacles RRT-based planners Conclusions Applicability of Lazy PRM to Spheres By Paul Elliott
Zvezda service module x Place start and goal Goal Start
Zvezda Service Module Place Start and Goal Goal Start
Place nodes Select a set of neighbors
Place nodes Select a set of Neighbors
A* search 16 18 x a* search
A* search 16 18 18 2 1 2 A* search
A* search Check nodes 一暑
A* search Check Nodes
Check nodes Check nodes 一暑
Check Nodes Check Nodes
A* search Check edges
A* search Check Edges
a Search Lazy prm algorithm Build roadmap qinit qgoal Start and Goal nodes Build roadm Uniform Dist Nodes Nearest Neighbors Shortest Node Path(a") nhanceme ent Remove Colliding node/edge No path found Collision Check edges Collisio
A* Search Lazy PRM Algorithm Build Roadmap Start and Goal Nodes Uniform Dist Nodes Nearest Neighbors Build Roadmap Shortest Path (A*) Check Nodes Check Edges Remove Colliding node/edge Node Enhancement Collision Collision No path found qinit, qgoal
Lazy PRM algorithm Shortest Path(A") it goal Heuristic= distance to Build roadmap the goal Path length-distance between nodes Shortest Path(A") Enhancement Remove Colliding node/edge No path found Collision Check nodes Collision Check ed Lazy prm algorithm ■ Check nodes& Edges qinit qgoal Search from Start and Build Roadmap End for collisions First check nodes then Edges Shortest Node Path(a") nhanceme ent Remove Colliding node/edge No path found Collision eck Nodes Collisio Check edg
Lazy PRM Algorithm Shortest Path (A*) Heuristic = distance to the goal Path length = distance between nodes Build Roadmap Shortest Path (A*) Check Nodes Check Edges Remove Colliding node/edge Node Enhancement Collision Collision No path found qinit, qgoal Lazy PRM Algorithm Check Nodes & Edges Search from Start and End for collisions First check Nodes then Edges Build Roadmap Shortest Path (A*) Check Nodes Check Edges Remove Colliding node/edge Node Enhancement Collision Collision No path found qinit, qgoal