Collaborative Multi Agent Physical Search with Probabilistic Knowledge

Noam Hazon, Yonatan Aumann, Sarit KrausIJCAI 2009 · OpenReview

Abstract

This paper considers the setting wherein a group of agents (e.g., robots) is seeking to obtain a given tangible good, potentially available at different locations in a physical environment. Traveling between locations, as well as acquiring the good at any given location consumes from the resources available to the agents (e.g., battery charge). The availability of the good at any given location, as well as the exact cost of acquiring the good at the location is not fully known in advance, and observed only upon physically arriving at the location. However, apriori probabilities on the availability and potential cost are provided. Given such as setting, the problem is to find a strategy/plan that maximizes the probability of acquiring the good while minimizing resource consumption. Sample applications include agents in exploration and patrol missions, e.g., rovers on Mars seeking to mine a specific mineral. Although this model captures many real world scenarios, it has not been investigated so far. We focus on the case where locations are aligned along a path, and study several variants of the problem, analyzing the effects of communication and coordination. For the case that agents can communicate, we present a polynomial algorithm that works for any fixed number of agents. For noncommunicating agents, we present a polynomial algorithm that is suitable for any number of agents. Finally, we analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities.

Imagine a fleet of rovers on Mars tasked with finding a specific mineral. Satellite data provides a "best guess" of where the mineral might be and the likely energy required to mine it, but the ground truth is only revealed upon physical arrival at a site. Every meter traveled and every mining attempt consumes a rover's limited battery. This scenario highlights a critical gap in multi-agent research: most previous models assume a "shared bank account" for energy or fixed costs.

This paper introduces a more realistic framework characterized by:

  1. Individual Budgets: Each agent has its own private energy supply.
  2. Probabilistic Costs: The cost to acquire a "good" is a random variable, revealed only upon arrival.
  3. Resource Competition: Energy spent traveling is energy that cannot be spent on the primary task.

The authors address two primary optimization problems: Max-Probability (maximizing the success rate given fixed budgets) and Min-Budget (minimizing energy allotment to reach a target success rate).

Figure 1: A 1D path search problem with two agents, individual budgets, and probabilistic acquisition costs at specific locations.

Methodology: 1D Path Setting and Separation Lemmata

The researchers focus on a 1D path setting, where sites are arranged linearly. While simplified, many complex 2D coverage algorithms decompose environments into such paths (e.g., lawnmower patterns). The paper employs Dynamic Programming (DP) to construct optimal strategies. To maintain tractability, the authors prove several "Separation Lemmata," demonstrating that in an optimal strategy, agents generally should not cross paths or redundantly search the same areas unless specific conditions are met.

Figure 2: Potential movement strategies (a, b, c) for multiple agents on a path, used to derive optimal separation lemmata.

For the Communicating Agents scenario, the authors introduce Cascading Orders. This scheduling method ensures agents with smaller budgets move first or scout for agents with larger budgets, preserving the most "capable" robots for the most resource-intensive tasks.

Key Insights and Complexity

  • Individual Budget Complexity: Shifting from a shared to an individual budget fundamentally alters the problem. In the non-communicating case with heterogeneous budgets, the "Min-Budget" problem becomes NP-hard.
  • Communication as a Force Multiplier: Communication enables "assistance." A low-energy robot can scout a site; if the cost is too high, it can call in a high-energy teammate. This creates a scheduling challenge solved by the cascading order approach.
  • Consistency in Heterogeneity: For robots with different capabilities (e.g., varying drill efficiencies), the authors assume "consistency"—if Robot A outperforms Robot B at one site, it must do so at others. This allows polynomial algorithms to remain valid for diverse teams.

Key Results

The paper establishes several algorithmic bounds:

  • Non-Communicating Agents: A polynomial-time algorithm exists for the Max-Probability problem for any number of agents.
  • Identical vs. Distinct Budgets: For non-communicating agents, the Min-Budget problem is polynomial if all robots have identical energy, but NP-hard if budgets differ.
  • Communicating Agents: Polynomial-time algorithms were developed for both Max-Probability and Min-Budget, provided the number of agents and cost levels are fixed. The algorithm runs in $O(m^3k^2)$ time, where $m$ is the number of sites and $k$ is the number of agents.

Conclusion and Future Directions

While the 1D constraint is a strong starting point, the authors acknowledge that search in general metric spaces remains NP-complete even for a single agent. Furthermore, the current model assumes a search for a single item; multi-item search likely increases complexity significantly. Future work includes extending these algorithms to complex 2D grids and exploring scenarios with differing travel efficiencies among agents.

Summary updated

Abstract

This paper considers the setting wherein a group of agents (e.g., robots) is seeking to obtain a given tangible good, potentially available at different locations in a physical environment. Traveling between locations, as well as acquiring the good at any given location consumes from the resources available to the agents (e.g., battery charge). The availability of the good at any given location, as well as the exact cost of acquiring the good at the location is not fully known in advance, and observed only upon physically arriving at the location. However, apriori probabilities on the availability and potential cost are provided. Given such as setting, the problem is to find a strategy/plan that maximizes the probability of acquiring the good while minimizing resource consumption. Sample applications include agents in exploration and patrol missions, e.g., rovers on Mars seeking to mine a specific mineral. Although this model captures many real world scenarios, it has not been investigated so far. We focus on the case where locations are aligned along a path, and study several variants of the problem, analyzing the effects of communication and coordination. For the case that agents can communicate, we present a polynomial algorithm that works for any fixed number of agents. For noncommunicating agents, we present a polynomial algorithm that is suitable for any number of agents. Finally, we analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities.
BibTeX
@inproceedings{hazon2009collaborative,
  author = {Noam Hazon and Yonatan Aumann and Sarit Kraus},
  title = {{Collaborative Multi Agent Physical Search with Probabilistic Knowledge}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=SkZPgrGu-r},
}
Figure