Multi-Agent Systems

Task allocation and scheduling is a well-studied problem in multi-agent systems, dealing with assigning agent resources to different tasks. It has applications well beyond robotics, including airline and post office scheduling and mission planning.

Task allocation with single-task robots, multi-robot tasks, and instantaneous assignment has been shown to be strongly NP-hard. Although this problem has been studied extensively, few efficient approximation algorithms have been provided given its inherent complexity. We provide discussion and analysis of two natural greedy heuristics for solving this problem, then introduce a new greedy heuristic that considers inter-task resource constraints to approximate the influence between different assignments. Instead of only looking at the utility of an assignment, our approach computes the expected loss of utility, due to the assigned robots and task, as an offset, and uses the offset utility for making the greedy choice. A formal analysis of the new heuristic shows that solution quality is bounded by two different factors, and we provide a new algorithm to approximate the heuristic for improved performance.

It is well understood that, through cooperation, multiple agents can achieve tasks that are unachievable by a single agent. However, there had been no formal characterization of situations where cooperation is required to achieve a goal, thus warranting the use of multiple agents. We provide such a formal characterization for multi-agent planning problems with sequential action execution.

We first show that determining whether there is required cooperation is, in general, intractable even in this limited setting, so we start our analysis with a subset of more restrictive problems where agents are homogeneous. For such problems, we identify two conditions that can cause required cooperation: when neither holds, the problem is single-agent solvable, and otherwise we provide upper bounds on the minimum number of agents required. For the remaining problems with heterogeneous agents, we further divide them into two subsets, and for one of these we propose the concept of a transformer agent to reduce the number of agents that need to be considered, which is used to improve planning performance.

This project addresses the multi-agent pathfinding problem in distributed systems that are subject to limited sensing and communication range. Cooperative pathfinding is typically addressed in one of two ways in the literature: fully coupled approaches consider all robots together and construct plans simultaneously, while decoupled approaches construct plans for only a subset of robots at a time. Decoupled approaches can be much faster, but are often suboptimal and incomplete, and the few decoupled approaches that do achieve completeness typically assume access to global information, which may not be available in distributed robotic systems.

We provide a window-based approach to cooperative pathfinding with limited sensing and communication range, called DisCoF. Robots are assumed to be fully decoupled initially, and may gradually increase their level of coupling online and in a distributed fashion; in cases where global information is needed to solve a problem instance, DisCoF eventually couples all robots together. DisCoF represents an inherently online approach, since robots may only be aware of a subset of robots in the environment at any given time and therefore lack enough information to determine non-conflicting plans with all other robots. A completeness analysis of DisCoF is provided.