Robot Motion Planning

Robots are capable of doing every wonderful and challenging task you want them to do, provided that the robots are made capable of masterminding the missions that you desire. Planning deals with the intelligence of making smart moves to even vague and dumb task definitions, rather than the other way round. Motion planning is the problem of enabling the robots run for you or run from you, without causing injury to anyone/anything movable or immovable. Even humans stumble when walking for which a common and recent example is texting and walking in characteristic scenarios. Nevertheless, asking the humans to teach the art of navigation to robots is the challenge taken in the course. Luckily we have standard tools for teaching and cheating, which is what the course is about. And if you succeed, those scary science fiction robots may just get real, a small but valid possibility!  

In this course, we study how the robots can move from one place to the other, without colliding, while making quality navigation plans in computationally less time. Attempt is to make the robot avoid small to big obstacles, structured and unstructured obstacles, static and dynamic obstacles, and complex mazes to wide open spaces; while triumphantly reaching the goal. Quicker calculations imply faster robots with more capability to handle sudden or dynamic changes in the environment. A variety of methods would be discussed including those coming from the domains of artificial intelligence, soft computing and from the general walking, running and quarrelling principles of the students.  

Syllabus

S. No. Topic Details
Core Topics
1. Introduction to Mobile Robotics Hardware, Software, Vision, Localization, Mapping, Planning, Control, HRI, real life examples, and related topics
2. Introduction to Robot Motion Planning Variants, Optimality, Completeness, Soundness, Mathematical Formulation, Real World Examples, Planning and Re-planning, Online Planning, Workspace and Configuration Space, Smoothness, Path Cost, Clearance, Structured and Unstructured Environments, Deliberative and Reactive methods, Anytime Algorithms
3. Configuration Spaces Definitions, Representations, Walkthrough with examples involving different kinds of robots and multi-robot system, Holonomic and Non-holonomic Constraints, Topology, Homeomorphism, Diffeomorphism, Manifolds
4. Collision Detection Topological Maps, Structured Maps, Un-structured Maps, Distance Functions, Mesh and Bounded Box Approaches, Collision detection between different regular shaped objects/regular objects in an unstructured environment
5. Bug Algorithms Bug0/Bug Zapper, Bug 1, Bug 2, Tangent Bug, Assessment of optimality and completeness
6. A* Algorithm - An Introduction States, Actions, Graph Formulation, Costs, Heuristics, Pseudo-code and Working of A*Algorithm
7. A* Algorithm in Robot Motion Planning Problem Formulation, Resolution-optimality, Resolution-completeness, Effect of resolution, Planning for non point robots, Planning with robot's dynamics, Post-processing and smoothing techniques
8. Potential Approaches Potential Modeling, Artificial Potential Fields, Gradient Descend, Examples with robots with proximity sensors and vision based approaches, Problems on narrow corridors, equi-potential/getting un-stuck, Bushfire Algorithm, Wave-front planner, Navigation Functions, Implementations in Workspace and Configuration Spaces, Elastic Strip
9. Roadmap Approaches Roadmaps, Visibility graphs, Deformation Retracts, Voronoi, Generalized Voronoi Diagram, Generalized Voronoi Graph
10. Cell Decomposition Approaches Trapezoidal Decomposition, Morse Cell Decomposition, Boustrophedon Decomposition, Bushfire Decomposition, Wave-front Decomposition, Triangular Decomposition, Quad-tree approach, Framed Quad-tree, Cells with variable sizes, Homotopy
11. Sampling Based Approaches -1: Probabilistic Roadmaps Introduction to sampling based approaches, single query algorithms, multi-query algorithms, sampling, computing vertices, constructing edges, local planners, connection with k-closest neighbors, connection with radius of k, edges by reversible and non-reversible local planner, collision-checking, post-processing, smoothing, probabilistic completeness, probabilistic optimality.
12. Sampling Based Approaches -2: Advanced Probabilistic Roadmaps Obstacle based PRM, Gaussian Roadmap, Bridge Test, roadmaps without cycles, Visibility PRM, Manipulability based PRM, Connection sampling, combination of sampling techniques, connecting disjoint graphs, lazy evaluations, Visibility PRM, Adaptive Roadmap, Elastic Roadmap
13. Sampling Based Approaches -3: Rapidly-exploring Random Trees EST, RRT, bidirectional RRT, RRT-Connect, RRG/RRT*, Kinodynamic planning, goal based sampling, SBL, sampling based roadmap of trees, parallel RRT , multi-tree approaches
14. Reactive Approaches Vector Field Histogram (VFH), Basics of VFH+ and VFH*, Velocity Obstacles
A Brief Overview of the following topics
15 Planning using Optimization Techniques Introduction to optimization and Genetic Algorithm, Individual representation, variable sized individual, fitness function, evolutionary operators, planning using grammatical evolution
16. Planning using Fuzzy Logic and Neural Networks Problem Modeling and use of Fuzzy Logic and Neural Networks for Robot Motion Planning, Shunting equation based navigation
17. Reinforcement Learning Introduction to RL, problem formulation, Q-Learning
18. Multi-Robot Motion Planning and Coordination Centralized techniques, decentralized techniques, with communication and without communication, prioritization, coordination using reactive planning, mission planning
19. Motion Planning using Hybrid Algorithms 2-layer planning, multi-layer planning, ensemble of algorithms, global and local planning
20. Motion Planning for Autonomous Vehicles  

Lab Syllabus

S. No. Topic
Playing with Simulators
1. Installing and Playing with Open Motion Planning Laboratory (OMPL)
2, Benchmarking in OMPL
3. Installing and Playing with MoveIt
4. Benchmarking with MoveIt
Programming
5. Installing and Playing with Open Motion Planning Laboratory (OMPL)
6. Collision Detection and Configuration Spaces
7. Motion Planning using PRM
8. Writing a simple planner using OMPL/Moveit
9. Motion Planning using RRT
10. Motion Planning using Visibility Roadmap
11. Motion Planning using Optimization
Presentations
12. Class Presentation on one paper related to the course

Pre-Requisites

Passion to learn new techniques, churn your brains and think a lot is mandatory. Some knowledge of search techniques in artificial intelligence, general principles of artificial intelligence, algorithms, soft computing, coordinate geometry and some programming skills are all desirable, though not necessary. An introduction to mobile robotics is taken as a part of the course, before delving into the particular problem of planning.

Text/Reference Material

Myself on:

And also on:

Contact

Dr. Rahul Kala
Assistant Professor,
IIIT Allahabad,

Phone: +91 532 299 2117
Mobile: +91 7054 292 063
E-mail: rkala@iiita.ac.in, rkala001@gmail.com