《认知机器人》（英文版） Probabilistic methods for Kinodynamic Path Planning

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