Multi-Agent Patrolling under Uncertainty and Threats

We investigate a multi-agent patrolling problem where information is distributed alongside threats in environments with uncertainties. Specifically, the information and threat at each location are independently modelled as multi-state Markov chains, whose states are not observed until the location is visited by an agent. While agents will obtain information at a location, they may also suffer damage from the threat at that location. Therefore, the goal of the agents is to gather as much information as possible while mitigating the damage incurred. To address this challenge, we formulate the single-agent patrolling problem as a Partially Observable Markov Decision Process (POMDP) and propose a computationally efficient algorithm to solve this model. Building upon this, to compute patrols for multiple agents, the single-agent algorithm is extended for each agent with the aim of maximising its marginal contribution to the team. We empirically evaluate our algorithm on problems of multi-agent patrolling and show that it outperforms a baseline algorithm up to 44% for 10 agents and by 21% for 15 agents in large domains.本研究针对存在不确定性的环境中信息与威胁共存的多智能体巡逻问题展开探究。具体而言，每个位置的信息与威胁均被独立建模为多状态马尔可夫链（Markov Chain），且仅当智能体到访该位置时，才能观测到其当前状态。尽管智能体可在到访位置获取信息，但同时也可能遭受该位置威胁带来的损伤。因此，智能体的目标是在尽可能收集信息的同时，降低所遭受的损伤。为应对该挑战，本研究将单智能体巡逻问题建模为部分可观察马尔可夫决策过程（Partially Observable Markov Decision Process, POMDP），并提出一种计算高效的算法以求解该模型。在此基础上，为生成多智能体巡逻策略，本研究将单智能体算法推广至多智能体场景，使每个智能体以最大化其对团队的边际贡献为目标。本研究在多智能体巡逻问题上对所提算法进行了实证评估，结果显示，在大规模环境中，该算法在10智能体场景下较基线算法性能提升最高可达44%，在15智能体场景下提升21%。