Ongoing Projects

A great way to get hands-on experience with the field of algorithmic robot motion planning is to participate in a semester-long project (all while getting academic credit). These projects are aimed both for advanced undergraduate students as well as graduate students taking their first steps conducting research. Prospective students are expected to be hard working and independent. In contrast to class exercises, most of these projects contain some research element – this means that the solutions to some of the challenges posed are not clear upfront and creative solutions may be the basis of a Masters thesis.

Each project contains the prerequisite courses and a general description, typically with the relevant paper(s) mentioned. If you are interested in working on one of these projects please reach out to me with an email describing your background and the project(s) that you are interested in (if you want to suggest your own project – great!). Make sure you have the necessary background, carefully read the project description and relevant papers – this will allow us to have a meaningful and productive discussion when we meet.

Redundant Inspection Planning

Picture for Redundant Inspection Planning
Supervisor(s):Prof. Oren Salzman, Projects
Requirements:Advanced topics in robotics (236610)
From a minimally-invasive medical robot automatically inspecting the surface of a diseased organ to an autonomous quadcopter inspecting the structure of a bridge, robots in a variety of scenarios must plan their motions to efficiently inspect regions of interest. These are examples of robot-inspection planning tasks which arise in diverse applications. Here, we are tasked with planning motions for a robot that enable it to efficiently inspect a region of interest using its on-board sensors. Such an inspection plan should not only inspect the region of interest but also obey the robot's kinematic constraints, avoid obstacles (e.g., parts of a bridge or sensitive anatomical structures in bridge inspection and medical applications, respectively), and minimize some metric (such as time to completion or distance traveled). Inspection planning is extremely challenging and naively-computed inspection plans may enable inspection of only a subset of the region of interest and may be highly suboptimal.
more info

However, computing a high-quality inspection plan is important for many applications, e.g., a medical diagnostic inspection plan should minimize procedure duration to decrease the amount of time a patient is under anesthesia, all while thoroughly inspecting the region of interest. In this project we consider the problem of redundant inspection planning. Specifically, given a set of points of interest and some parameter k, we want to compute a path such that every point of interest is seen from at least k different configurations.

Additional details can be found here.

Efficient Multi-Agent Path Finding (MAPF) via Massive Preprocessing

Picture for Efficient Multi-Agent Path Finding (MAPF) via Massive Preprocessing
Supervisor(s):Prof. Oren Salzman
Requirements:Intro to AI (236501)
MAPF problems are typically defined as a one-shot problem where a query is provided to the algorithm and it is tasked with computing a collision-free path for a fleet of agents between their respective start and target locations. However, in many cases the environment is known in advance (e.g., in warehouses) and the system is tasked with answering multiple queries. While this layout is constantly changing, at any given point of time, the vast majority of the environment remains unchanged when compared to the original layout.
more info
Thus, when solving the MAPF problem, we are often given the additional flexibility of preprocessing the environment in order to efficiently answer multiple MAPF problems in a query phase-an approach that was shown to be extremely useful for the continuous motion-planning problem. Roughly speaking, in this project we are exploring how learning from experience can assist in coping with computationally-hard problems. Additional details can be found here.

Multi-Objective Multi-Agent Path Finding (MAPF)

Picture for Multi-Objective Multi-Agent Path Finding (MAPF)
Supervisor(s):Prof. Oren Salzman
Requirements:Intro to AI (236501)
In this project we will explore the problem of computing solutions to the MAPF problem that balance between the makespan and the flowtime. This is a specific instance of a general family of problems called Bi-criteria optimization. Here we wish to compute all solutions where no solution is strictly better then the others for both cost functions, a set called the Pareto-optimal frontier. Additional details can be found here.

Time Efficient Curvature Constrained Planning

Picture for Time Efficient Curvature Constrained Planning
Supervisor(s):Prof. Oren Salzman
In this project, we are interested in computing curvature constrained paths for a robot moving amidst obstacles in the plane. Namely, we have a robot that has a minimum turning radius that it can follow. This constraint allows to model a wide range of systems such as UAVs and steerable needles and has attracted increasing attention in the planning community. Here, we are interested in a non-trivial cost function---minimizing travel time (and not path length). In many settings, taking longer manoeuvres at a higher speed is favorable (with respect to travel time) when compared to short, but slow, manoeuvres. In the project, we will explore efficient algorithmic methods to perform this task based on search algorithms. Additional details can be found here.

Towards Understanding Domain Coherence

Picture for Towards Understanding Domain Coherence
Supervisor(s):Prof. Oren Salzman
Requirements:Advanced topics in robotics (236610) / Introduction to Robotics (236927 or 046212)
Informally speaking, domain coherence is the property that a domain contains either ``similar'' problems or ``similar'' robots (or both). Consequently, domain coherence implies that given a motion-planning problem and two ``similar'' robots (for example, two manipulators with roughly the same link lengths, payload, joint limitations, etc.), then a solution obtained for the first robot is ``similar'' to a solution obtained for the second robot. Surprisingly, this intuitive notion is quite challenging to formalize. In this project we will take a data-driven approach to formalizing this notion and demonstrate its usefulness in motion-planning problems.

Resilient motion planning

Supervisor(s):Prof. Oren Salzman
Requirements:Advanced topics in robotics (236610) / Introduction to Robotics (236927 or 046212)
In this project we will investigate the problem of resilient motion planning. Here, we are interested in computing a path that can still be executed even if one of the robot's system's fails. Specifically, we will look at robot manipulators which often have some redundancy built in. For example, to reach any point in space, we are required to have a six degree of freedom (DOF) arm. However, many manipulators are endowed with seven DOFs. This extra flexibility allows a planner to choose between many options when attempting to connect two points. Typically, one option is chosen and the rest are discarded. In this project we will investigate how this redundancy can be used in a systematic way in order to achieve a resilient motion planner. Additional details can be found here.