Magellan: A Risk-bounded Plan Executive for Autonomous Mobile Agents

Autonomous mobile agents are being tasked to perform increasingly complex, coordinated missions that require achieving multiple goals over long horizons and in risky environments. This requires a tight coupling between activity and motion planning– commitments made in an activity plan and its supporting motion plan can strongly influence overall behavior and, if not chosen in coordination, can lead to poor performance or failure. These missions also require robust plan execution, adapting to disturbances on the fly. Current plan executives are myopic in that they focus on a short planning horizon and weakly characterize behavior beyond this horizon. For long horizon missions, this produces highly suboptimal and brittle behavior. This thesis presents Magellan, a plan executive for long duration missions with multiple autonomous mobile agents. Magellan employs a receding horizon trajectory optimization approach that avoids myopia by generating precise trajectories over a limited horizon while guiding these motions beyond this horizon by using an effective heuristic that considers the constraints and objectives of the full activity plan. Magellan also uses this heuristic throughout execution to continuously monitor and detect plan infeasibilities early on, while reporting the source of unrecoverable constraint violations to the activity planner for re-planning. We demonstrate that Magellan achieves an order of magnitude improvement in solution quality over the state of the art for multi-agent problems of arbitrary size. Autonomous mobile agents often operate in hazardous environments, where safety is essential. These agents can guarantee bounded risk during planning by analyzing their stochastic dynamics. These dynamics are complicated by their non-linearity. Most state-of-the-art methods require a simple closed-form dynamics model to verify plan correctness and safety; however, modern robotic systems often have dynamics modeled by a complex analytical form that is learned from data, such as a deep neural network. Thus, there is a need to perform efficient trajectory planning using learned dynamics models while guaranteeing bounded risk. This thesis also presents LaPlaSS, a novel "generate-and-validate" approach to risk-bounded planning in which a planner generates a candidate trajectory quickly, using an approximate linear dynamics model, and the validator assesses candidate risk against an accurate model. When a candidate takes excessive risk, the validator supplies the planner with additional safety constraints. Key to LaPlaSS is to learn a simple, low-dimensional approximate model, used for candidate generation, and an accurate stochastic model, used for validation. LaPlaSS uses a variational autoencoder to learn a simple linear model in a higher-dimensional latent space, which it uses to generate candidate trajectories. The VAEalso provides an accurate stochastic model, which the validator samples to evaluate candidate risk. We demonstrate that LaPlaSS can generate trajectory plans with bounded risk for a real-world agent with learned dynamics and is an order of magnitude more efficient than the state of the art.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Reeves, Marlyse H.

Advisor dc:contributor.advisor

• Williams, Brian C.

Statement dc:rights

• Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
• Copyright retained by author(s)

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nc-nd/4.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/156578

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/156578