Controlling Growing Tasks with Heterogeneous Agents

James Parker, Maria L. GiniIJCAI 2016

Introduction

In many real-world scenarios, tasks are not static. A small brush fire can quickly escalate into a massive forest fire, and a localized disease outbreak can become a global pandemic if not addressed promptly. Traditional multi-agent task allocation (MATA) often assumes fixed task costs, but in these critical domains, the cost of a task is a function of time and the resources allocated to it. This paper explores how a heterogeneous fleet of agents—robots with varying capabilities—can be optimized to minimize the total damage caused by such growing tasks.

The Challenge of Growing Tasks

The core difficulty lies in the temporal dependency of task costs. If resources are spread too thin, tasks continue to grow, potentially reaching a point where they are impossible to contain. The authors focus on minimizing the total accumulated growth, such as the total area burned in a fire, rather than just the time to completion.

Figure 1: Illustration of task cost dynamics over time. Task 2 initially grows before being contained, while Task 1 is reduced immediately.

Theoretical analysis reveals that the optimal strategy depends on the "shape" of the growth function. For tasks with monotonic deceleration (where growth slows as the task gets larger), the mathematically optimal approach is to "swarm" the smallest tasks first. This prevents small problems from becoming large ones, creating a more efficient containment cycle.

Algorithmic Solutions for Heterogeneous Fleets

Real-world deployment introduces complexities like travel time and agent heterogeneity. To address these, the authors propose two primary algorithms:

  • HLFF (Heterogeneous Latest Finishing First): This algorithm is tailored for scenarios with high travel costs. It uses a Mixed-Integer Linear Program (MILP) to solve a variation of the bin-packing problem, matching specific agent work rates to the required "work units" of each task.
  • HRT-LFF (Heterogeneous Real-Time LFF): Designed for dynamic environments where agents can move between tasks, this heuristic uses real-time simulations. It evaluates the impact of reassigning specific agents to different tasks, choosing the configuration that minimizes predicted total growth.

The use of heterogeneous agents allows for finer granularity. Instead of wasting a high-capacity agent on a nearly finished task, the system can dispatch a low-capacity "scout" to finish it, reserving the "heavy hitters" for larger, more critical fires.

Experimental Evaluation

The algorithms were tested using the RoboCup Rescue Agent Simulator, a benchmark for disaster response coordination. The researchers modeled fire growth as an exponential function and tested the system across various urban maps, including "Virtual City" and "Paris" layouts. Agents were divided into three classes with 100%, 50%, and 10% capacity.

Results and Discussion

The HRT-LFF algorithm consistently outperformed baseline strategies, such as uniform resource distribution or focusing all agents on a single task.

Figure 4: Comparison of building preservation percentages across different maps and strategies. HRT-LFF shows superior performance in nearly all scenarios.

As shown in the results table, HRT-LFF achieved significantly higher percentages of intact buildings. For instance, in the "VC 3" map, HRT-LFF preserved 65.35% of buildings, a substantial improvement over the 40.24% achieved by the "All-on-One" strategy. These results demonstrate that reasoning about individual agent capabilities and the specific growth dynamics of tasks provides a critical advantage in high-stakes environments.

Conclusion

This research highlights the importance of considering task growth and agent heterogeneity in multi-robot systems. By prioritizing smaller tasks in decelerating growth scenarios and leveraging the diverse capabilities of a robot fleet, we can significantly reduce the total damage in disaster response and other time-sensitive domains. Future work will look into decentralized control and handling uncertainty in task growth models.

Summary updated

BibTeX
@inproceedings{parker2016controlling,
  author = {James Parker and Maria L. Gini},
  title = {{Controlling Growing Tasks with Heterogeneous Agents}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}

Loading related content...

Figure