Planning and Decision Making

This course provides an overview of motion planning and decision-making techniques and their practical application in robotics.

Planning and Decision-making are critical components of autonomy in robotic systems. These components are responsible for making decisions that range from path planning and motion planning to coverage and task planning to taking actions that help robots understand the world around them better. This course studies underlying algorithmic techniques used for planning and decision-making in robotics and examines case studies in ground and aerial robots, mobile manipulation platforms and multi-robot systems. The students will learn the algorithms and implement them in a series of programming-based projects.

In particular, we will first cover the fundamentals of planning (workspace, configuration space, representation of obstacles and robot models). We will then cover a broad set of methods, which include reactive methods and feedback control; discrete, combinatorial and probabilistic planning; planning under differential constraints; planning under uncertainty; learning in planning; and planning for multi-robot systems. Finally, we will briefly touch upon task assignment and vehicle routing.

Course structure:

Introduction

• Fundamentals: 3D rotations, configuration space, algorithm properties

• Differential constraints: recap of modeling en control of manipulators, ground robots, aerial robots

• Graph-search fundamentals (depth/breadth first, Dijkstra, A*, heuristics)

• Combinatorial algorithms (cell decomposition, shortest-path roadmaps, motion primitives)

• Sampling-based algorithms (PRM, RRT, RRT*)

• Reactive algorithms: collision avoidance, potential fields, velocity obstacles

• Kinodynamic planning

• Trajectory optimization (fundamentals, global, local, Model Predictive Control)

• Planning under uncertainty (Markov Decision Processes, learning)

• Multi-robot motion planning (joint configuration, optimization-based, coverage)

• Task assignment (Hungarian, auction, linear program)

• Intro to vehicle routing