Robot Motion Planning using A* (Cyrill Stachniss)

Robot Motion Planning using A*
Cyrill Stachniss, Fall 2020

[@morrobotik8105]

Thank you Professor.

[@tanjabz6599]

🤖 Lecture Contents 🤖 📌 (0:00:00) Motion Planning (Intro) 📌 (0:02:10) Robot Motion Planning using A* 📌 (0:02:28) Motion Planning Problem 📌 (0:05:17) ...in Dynamic Environments 📌 (0:09:57) Key Challenges 📌 (0:56:23) Classic Layered Architecture 📌 (0:14:31) Motion Planning Problem 📌 (0:16:36) Configuration Space 📌 (0:23:35) C-Space Discretization 📌 (0:26:25) Search 📌 (0:34:35) Uninformed Search 📌 (0:39:07) Cost Sensitive Search 📌 (0:42:10) Uniform Cost Search and BFS 📌 (0:42:38) UCS and Dijkstra 📌 (0:44:08) Informed Search Techniques 📌 (0:45:51) Greedy Search 📌 (0:48:10) A* Search 📌 (0:49:18) A*: Developed for Shakey 📌 (0:50:29) A* Search for Path Planning 📌 (0:53:32) A* Search Example 📌 (0:55:29) A*: Minimize Accumulated and Estimated Cost 📌 (0:57:31) Heuristic for A* 📌 (1:02:11) A* Flow Chart 📌 (1:07:10) Application to Robot Navigation 📌 (1:07:39) Path Planning for Robotics in a Grid World 📌 (1:08:44) Typical Assumption used in A*-Based Path Planning 📌 (1:11:40) Potential Problems 📌 (1:15:06) Convolution of the Grid Map 📌 (1:17:23) Example: Map Convolution 📌 (1:18:35) Convolution 📌 (1:19:06) A* in Convolved Maps 📌 (1:20:27) Heuristic via Dijkstra's Algo. 📌 (1:23:37) High-Dimentional Spaces 📌 (1:24:08) 5D-Planning - use Velocities in the Configuration Space 📌 (1:26:01) The Search Space 📌 (1:27:41) The Main Steps of the Algorithm 📌 (1:29:23) Updating the Grid Map 📌 (1:30:01) Finding a Path in the 2D-Space 📌 (1:31:04) Restricting the Search Space 📌 (1:32:00) Space Restriction 📌 (1:32:42) Finding a Path in the 5d-Space 📌 (1:33:25) Example 📌 (1:35:19) Comparison to the Optimum 📌 (1:36:28) Summary

[@AndreiChegurovRobotics]

Great materials, thx! Find this very helpful during investigation of motion-primitives based trajectory search.

[@ColinDH12345]

Appreciate these videos. Excellent content. Thank you :-)

[@shaohuachen2482]

Thank you, Professor!

[@RZtronics]

Great Content!

[@1volkansezer]

Dear Cyrill, thanks for your efforts to provide chance to everyone in the world to learn these very important subjects. This is a gift for everyone, I really appreciate your work. And one question, isn't it better to show the search algorithms on "graphs" instead of "trees" since real applications on autonomous robots are generally based on graphs. An occupancy grid map or a roadmap network etc. are in graph structure, not in a tree format right?

[@MultiBussen]

True, for instance, the configuration space in the search example is a graph. I think he uses trees for pedagogical reasons, as it is easier to see what are the neighbors and what we have visited before

[@hene6539]

Perfect!

[@welidbenchouche]

amazing video, where can we find code for this please?

[@prashantupadhyay6019]

Can you please tell, what is the meaning of costly trajectory function, as you mention some trajectory have higher cost function.

[@CyrillStachniss]

Higher cost means typically longer in distance or longer to traverse, depends on you setup and definition of cost, ie what you want to minimize.

[@gezakiss8804]

Very nice lectures. One minor remark: The lecturer will make his lectures even more enjoyable if he looks up the pronunciation of these words: “because”; “occur”; “estimate” (as a verb, which sounds different from when it is a noun). All the best!