A Multitier Approach for Dynamic and Partially Observable Multiagent Path-Finding

Abstract

This paper introduces a novel Dynamic and Partially Observable Multiagent Path-Finding (DPO-MAPF) problem and presents a multitier solution approach accordingly. Unlike traditional MAPF problems with static obstacles, DPO-MAPF involves dynamically moving obstacles that are partially observable and exhibit unpredictable behavior. Our multitier solution approach combines centralized planning with decentralized execution. In the first tier, we apply state-of-the-art centralized and offline path planning techniques to navigate around static, known obstacles (e.g., walls, buildings, mountains). In the second tier, we propose a decentralized and online conflict resolution mechanism to handle the uncertainties introduced by partially observable and dynamically moving obstacles (e.g., humans, vehicles, animals, and so on). This resolution employs a metaheuristic-based revision process guided by a consensus protocol to ensure fair and efficient path allocation among agents. Extensive simulati ons validate the proposed framework, demonstrating its effectiveness in finding valid solutions while ensuring fairness and adaptability in dynamic and uncertain environments.

Keywords

Multiagent Path-Finding, Uncertainty, Ant Colony Optimization, Consensus

Methodology Overview

The methodology presented in the paper "A Multitier Approach for Dynamic and Partially Observable Multiagent Path-Finding" involves a two-tiered strategy to solve a Multiagent Path-Finding (MAPF) problem in environments with both static obstacles and partially observable, dynamically moving obstacles:

1. Centralized and Offline Planning

Initially, a centralized algorithm (e.g., CBSH2-RTC or EECBS) generates conflict-free paths for agents, considering only static obstacles such as walls and buildings. This phase is executed offline and provides an initial plan for each agent.

2. Decentralized and Online Conflict Resolution

Agents independently execute their initial paths. If conflicts arise with partially observable, dynamic obstacles (e.g., humans, vehicles), an online decentralized conflict resolution mechanism is triggered. This mechanism employs:

• A revising strategy using a metaheuristic method — specifically, Ant Colony Optimization (ACO) — to dynamically adjust agent paths.
• A consensus protocol (either Fair Token or Probability-Based) that prioritizes agents to ensure fairness and efficient conflict resolution.

This multitier methodology leverages the strengths of centralized approaches (global optimality and planning) and decentralized approaches (scalability and adaptability), enhancing agents' adaptability and fairness in complex, uncertain environments.

Figure 1. Illustration of the Proposed Multitier Approach

Figure 2. Fair Token Protocol

Algorithm 1. Proposed ACO for Revising Strategy

Equation 15

Equation 16 and 17

Simulation Setup

The simulation setup described in the paper is designed specifically to evaluate the multitier approach for the Dynamic and Partially Observable Multiagent Path-Finding (DPO-MAPF) problem, as shown in Figure 1. Below is a short description of its key features:

Simulation Framework

Environment

The simulation operates on grid-based environments represented as graphs, where cells correspond to nodes and agent movement between adjacent cells maps to graph edges.

Map Generation

• Various map sizes: 10×10, 15×15, 20×20, and 25×25.
• Static obstacles are randomly placed with densities of 5%, 10%, 15%, and 20%.
• 3 to 12 agents and dynamic obstacles are randomly initialized using unique random seeds for reproducibility.
• The maximum number of time steps is set to twice the Manhattan distance from the initial to goal position of each agent.

Dynamic Obstacles

These obstacles move unpredictably. Agents can only detect them within a limited local vision — a 5×5 grid centered on the agent.

Agent Actions

Each agent can perform the following actions: Up, Down, Left, Right, and Wait.

Simulation Objective

The goal is to guide agents safely from their initial positions to their goal destinations while handling partial observability and avoiding collisions.

Performance is assessed using the following metrics:

• Success Rate
• Runtime
• Optimality Gap
• Concession Difference
• Earth Mover’s Distance (EMD)

Implementation

The simulation framework is implemented in Python and made publicly available on GitHub to support reproducibility and further research.

This setup enables extensive experimental evaluation of the proposed multitier strategy, demonstrating its adaptability and effectiveness across a variety of dynamic, partially observable environments.

Figure 3. Illustration of the Simulation Framework

Results

Multitier Components

• Success Rate: Optimal solver (CBSH2-RTC) with Probability-Based protocol achieves the highest success rate (46.5%).
• No statistically significant difference observed between optimal and suboptimal solvers regarding success rate.

• Optimality Gap: No statistically significant differences between solver and protocol configurations. Gap remains approximately 4.2%–4.5%.

• Runtime: Fair Token protocol with suboptimal solver (EECBS) has longer runtimes due to evaluation of hypothetical conflicts for all agents.

• Fairness (Concession Difference): Fair Token protocol achieves the best fairness (0.42–0.43 max concession diff), while Probability-Based protocol shows the poorest fairness (0.71–0.80).

Revising Strategy Evaluation

• Success Rate: Enhanced ACO outperforms all other methods:
  • Enhanced ACO (44.7%)
  • Basic ACO (39.9%)
  • Only Waiting (23.5%)
  • No Revising (18.9%)
• Optimality Gap: Slight increase with Enhanced ACO (~4.47%) is justified by significant gains in success rate.
• Runtime: Basic ACO is the slowest (~1.92 sec). Enhanced ACO reduces runtime via early stopping and integration of a "wait" strategy.
• Path Revision Impact (EMD): Enhanced ACO leads to more significant path changes (higher EMD), which strongly correlates with improved success rates.

Key Takeaways

• The multitier framework balances centralized offline planning and decentralized online resolution effectively.
• Enhanced ACO substantially improves adaptability and agent performance in uncertain environments.
• Fair Token protocol excels in ensuring fairness among agents during conflict resolution.
• The results validate the proposed methodology's effectiveness in real-world-like, dynamic, partially observable MAPF scenarios.

Summary and Conclusion

This paper introduces the Dynamic and Partially Observable Multiagent Path-Finding (DPO-MAPF) problem, an extension of traditional MAPF that incorporates dynamic and partially observable obstacles.

To address this challenge, a multitier methodology is proposed, combining:

• Centralized offline planning for navigating around static obstacles using optimal or suboptimal solvers.
• Decentralized online conflict resolution utilizing Ant Colony Optimization (ACO) enhanced with consensus protocols to manage dynamic obstacles.

Experimental results demonstrate that:

• The multitier strategy significantly improves agent adaptability and success rates in uncertain environments.
• The Fair Token protocol effectively maintains fairness among agents during real-time conflict resolution.
• Enhanced ACO outperforms basic revising strategies in both success rate and runtime, with only a minor trade-off in optimality gap.

In conclusion, this multitier approach offers a robust, fair, and efficient framework for solving complex MAPF problems in dynamic, partially observable environments — providing a solid foundation for future research in decentralized multi-agent coordination and planning under uncertainty.

@conference{dogru2025multitier,
  author={Anıl Doğru and Amin Deldari Alamdari and Duru Balpınarlı and Reyhan Aydoğan},
  title={A Multitier Approach for Dynamic and Partially Observable Multiagent Path-Finding},
  booktitle={Proceedings of the 17th International Conference on Agents and Artificial Intelligence – Volume 3: ICAART},
  year={2025},
  pages={562–573},
  publisher={SciTePress},
  organization={INSTICC},
  doi={10.5220/0013159800003890},
  isbn={978-989-758-737-5},
  issn={2184-433X}}
    

TY  - CONF 

JO  - Proceedings of the 17th International Conference on Agents and Artificial Intelligence - Volume 3: ICAART
TI  - A Multitier Approach for Dynamic and Partially Observable Multiagent Path-Finding
SN  - 978-989-758-737-5
IS  - 2184-433X
AU  - Doğru, A.
AU  - Alamdari, A.
AU  - Balpınarlı, D.
AU  - Aydoğan, R.
PY  - 2025
SP  - 562
EP  - 573
DO  - 10.5220/0013159800003890
PB  - SciTePress