Task allocation and scheduling is a well studied problem in multi-agent systems which deals with assigning agent resources to different tasks. It has a variety of applications that go beyond robotics, such as airline and post office scheduling, mission planning and etc.
Task Allocation
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 pro- vided due to its inherent complexity. Firs, we provide discussions and analyses for two natural greedy heuristics for solving this problem. Then, a new greedy heuristic is introduced, which considers inter-task resource constraints to approximate the influence between different assignments in task allocation. Instead of only looking at the utility of the 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 is provided for the new heuristic, which reveals that the solution quality is bounded by two different factors. A new algorithm is then provided to approximate the new heuristic for performance improvement.
Y. Zhang, L.E. Parker
Considering inter-task resource constraints in task allocation
JAAMAS, 2013.
Required Cooperation
It is well understood that, through cooperation, multiple agents can achieve tasks that are unachievable by a single agent. However, there are no formal characterizations of situations where cooperation is required to achieve a goal, thus warranting the application 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 (RC) is in general intractable even in this limited setting. As a result, 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 RC. We establish that when none of these conditions hold, the problem is single-agent solvable; 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. For one of the subsets, we propose the concept of transformer agent to reduce the number of agents to be considered which is used to improve planning performance.
Y. Zhang, S. Sreedharan and S. Kambhampati
A Formal Analysis of Required Cooperation in Multi-agent Planning
ICAPS, 2016.
Distributed Pathfinding
The task here is to address the multi-agent pathfinding problem with distributed systems that are subject to limited sensing and communication range.
Cooperative pathfinding is often addressed in one of two ways in the literature. In fully coupled approaches, robots are considered together and the plans for all robots are constructed simultaneously. In decoupled approaches, the plans are constructed only for a subset of robots at a time. While decoupled approaches can be much faster than fully coupled approaches, they are often suboptimal and incomplete. Although there exist a few decoupled approaches that achieve completeness, global information (which makes global coordination possible) is assumed. Global information may not be accessible in distributed robotic systems. We provide a window-based approach to cooperative pathfinding with limited sensing and communication range in distributed systems (called DisCoF). In DisCoF, robots are assumed to be fully decoupled initially, and may gradually increase the level of coupling in an online and distributed fashion. In some cases, e.g., when global information is needed to solve the problem instance, DisCoF would eventually couple 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 point of time. Hence, they do not have enough information to determine non-conflicting plans with all the other robots. Completeness analysis of DisCoF is provided.
Y. Zhang, K. Kim and G. Fainekos
DisCoF: Cooperative Pathfinding in Distributed Systems with Limited Sensing and Communication Range
DARS, 2014.