Doctoral Thesis: Visibility-Aware Motion Planning

Gustavo Goretkin

Abstract:

The motion planning problem, of deciding how to move to achieve a goal, is ubiquitous in robotics.
In many robotics applications, there is a map of the environment that is generally useful, but typically outdated as it does not include information about unknown obstacles, such as clutter.

This thesis addresses the problem of planning for a robot with an onboard obstacle-detection sensor.
The planning objective is to remain safe with respect to unknown obstacles by guaranteeing that the robot will not move into any region of the workspace before the region is observed.

Although a great deal of work has addressed a version of this problem in which the “field of view” of the sensor is a sphere around the robot, there is very little work addressing robots with a narrow or occluded field of view.
We give a formal definition of the problem, which we call Visibility-Aware Motion Planning (VAMP), along with several solution methods with different computational trade-offs.
We demonstrate the behavior of these planning algorithms in illustrative planar domains.
The key to an efficient solution is to aggressively prune paths during planning.
We prove that the overall search strategy is sound and complete.

We demonstrate that motion planning problems such as minimum constraint removal, belief-space planning, and VAMP benefit from a path-dependent formulation, in which the state at a search node is represented implicitly by the path to that node.
The straightforward approach to computing the feasibility of a successor node in such a path-dependent formulation takes time linear in the path length to the node, in contrast to a (possibly very large) constant time for a more typical search formulation.
For long-horizon plans, this linear-time computation for each node becomes prohibitive.
To improve upon this, we introduce the use of a fully persistent spatial data structure (FPSDS).
We then focus on the application of the FPSDS in VAMP, by using a nearest-neighbor data structure to perform bounding-volume queries.

We demonstrate an asymptotic and practical improvement in the runtime of finding VAMP solutions in large domains.
To the best of our knowledge, this is the first use of a fully persistent data structure for accelerating motion planning.

Details

• Date: Monday, December 20
• Time: 11:00 am
• Category: Thesis Defense
• Location: 32-G449 (Kiva)

Additional Location Details:

Thesis Supervisors:
Leslie Pack Kaelbling
Tomás Lozano-Pérez
Nicholas Roy

All non-MIT in-person attendees will need to register for contact tracing purposes. You will be scanned into the room prior to the thesis defense using your MIT ID badge or the QR code generated by the registration link.

Please register in advance using this link:
https://tim-tickets.atlas-apps.mit.edu/NQeGxdqfLyGQJZ5H6

Zoom link:
please email goretkin@csail.mit.edu

If you have difficulty accessing the building, call (857) 264-6158 to be escorted.