Multi-Agent Planning Under Uncertainty

Other Titles


The development of foundational theory and validated algorithms for human-robot teams operating in complex environments, capable of adapting as knowledge of the environment and tasks evolves over time, is a crucial area of research. As data becomes available, there is a need for evolving planning strategies to effectively utilize the information. In the specific context of search and rescue (SaR) scenarios, the high-level goals are to locate survivors, simulate rescue by having humans meet survivors, and minimize the risk to human team members. Ultimately, we seek to improve human-cooperation under uncertainty, as well as team performance and safety. This thesis explores probabilistic driven multi-agent planning approaches, motivated by the challenges posed by SaR missions.First, we investigate the problem of multi-robot non-adversarial search. Uncertainty is present in the victim’s true location as only probabilistic information is available a priori. In this context, we seek to find the optimal (or near optimal) path that maximizes the likelihood that our search team can intercept the target given a mission deadline. We prove this problem to be NP-hard, and present the first set of Mixed-Integer Linear Programming (MILP) models to encompass multiple searchers, arbitrary capture ranges, and false negatives simultaneously. The adoption of MILP as a planning paradigm allows to leverage the powerful techniques of modern solvers, yielding better computational performance and, as a consequence, longer planning horizons than the previous state-of-the-art. We build upon the proposed models to incorporate the concept of danger,estimated through a human-robot shared scene perception scheme, allowing for environment knowledge to evolve throughout the mission. The trade-off between risk vs reward is explored through conditional planning, based on the distinct agents’ tolerances to danger. We then consider other tasks beyond search in our mission, and ultimately even the planned routes and completion of tasks are modeled in a probabilistic manner. We introduce a novel problem formulation that incorporates probabilistic knowledge of task requirements, dependencies between tasks and their relative locations, heterogeneity of agents’ capabilities and an environment that might change as the agents interact with it. Performance assessment of possible mission plans is thus based on probabilistic predictions and tangible reward concepts for team forming, another important aspect of SaR missions.

Journal / Series

Volume & Issue


141 pages


Date Issued




multi-agent; optimization; planning; probability; robotics; search and rescue


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Campbell, Mark

Committee Co-Chair

Committee Member

Ferrari, Silvia
Jung, Malte

Degree Discipline

Aerospace Engineering

Degree Name

Ph. D., Aerospace Engineering

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Attribution 4.0 International


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record