Multi-Agent Patrolling under Uncertainty and Threats.

Area of Science:

• Robotics
• Artificial Intelligence
• Operations Research

Background:

• Multi-agent systems face challenges in environments with uncertain information and threats.
• Distributed information and threats are often modeled using Markov chains, requiring agent interaction for state observation.
• Balancing information acquisition with damage mitigation is crucial for effective patrolling.

Purpose of the Study:

• To develop an efficient algorithm for multi-agent patrolling in uncertain environments.
• To formulate the single-agent patrolling problem as a Partially Observable Markov Decision Process (POMDP).
• To extend the single-agent solution for multi-agent coordination, maximizing individual contributions to the team objective.

Main Methods:

• Formulation of the single-agent patrolling problem as a Partially Observable Markov Decision Process (POMDP).
• Development of a computationally efficient algorithm to solve the single-agent POMDP.
• Extension of the single-agent algorithm for multi-agent scenarios, optimizing for marginal team contribution.

Main Results:

• The proposed algorithm effectively balances information gathering and threat mitigation.
• Empirical evaluations demonstrate significant performance improvements over a baseline algorithm.
• The algorithm achieved up to 44% improvement for 10 agents and 21% for 15 agents in large domains.

Conclusions:

• The developed POMDP-based approach provides an efficient solution for multi-agent patrolling under uncertainty.
• The method successfully enhances team performance by optimizing individual agent contributions.
• This research offers a valuable framework for designing robust multi-agent coordination strategies in complex environments.