Back to search

Cornell University

Multi-Agent Planning Under Uncertainty

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Aerospace Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Aerospace Engineering
Grantor
Cornell University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Asfora, Beatriz
Chair dc:contributor.chair
  • Campbell, Mark
Committee members dc:contributor.committeemember
  • Ferrari, Silvia
  • Jung, Malte

Subjects

dc:subject × 6

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16219537
Dc Identifier Other
ProQuest Submission ID: 13819
ProQuest Publication ID: 30573344

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Asfora, Beatriz. Multi-Agent Planning Under Uncertainty. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/114565