Planning Algorithms

Find collision-free paths. Search a grid map with Dijkstra and A* and drive a rover through a maze, then plan through spaces too big to grid: grow a random tree for one query, and build a roadmap that answers many.

What you'll learn

• >Dijkstra and A* with admissible heuristics
• >Rapidly-exploring random trees
• >Probabilistic roadmaps with Dijkstra queries

Before you start

You should be comfortable with basic Python: variables, loops and functions. We'll introduce the robotics and the maths as you go. The first visit downloads the physics engine and Python, about 20 MB, and later visits load from your browser's cache.

Steps

1. 1Dijkstra and A*Search a grid map for the cheapest path: evenly in every direction with Dijkstra, then steered towards the goal with A*.Configuration spaceDijkstra's algorithmA* and admissible heuristicsOpen
2. 2RRTGrow a random tree of collision-free motions from the start until it reaches the goal.Sampling-based planningNearest neighboursGoal biasPro
3. 3Probabilistic roadmapSample free configurations, link near neighbours into a graph once, then answer every query with a graph search.Roadmapsk-nearest neighboursDijkstra's algorithmPro