Fast and Adaptive Multi-Agent Planning under Collaborative Temporal Logic Tasks via Poset Products

Area of Science:

• Robotics
• Artificial Intelligence
• Formal Methods

Background:

• Coordinated planning is crucial for large-scale multi-agent systems in dynamic environments.
• Existing heuristic or learning-based methods lack performance guarantees.
• Formal methods offer verifiability for tasks with spatial-temporal requirements (e.g., linear temporal logic formulas) but face scalability issues.

Purpose of the Study:

• To develop a scalable planning paradigm for system-wide temporal task formulas in multi-agent systems.
• To overcome the exponential complexity bottleneck in traditional formal methods for task planning.
• To enable efficient and verifiable task planning for large fleets with complex, continuously released tasks.

Main Methods:

• Proposed a new planning paradigm avoiding direct Büchi automaton translation and synchronized products.
• Introduced an adaptive planning algorithm computing products of relaxed partially ordered sets (R-posets) on-the-fly.
• Assigned subtasks to agents while respecting ordering constraints.

Main Results:

• Achieved polynomial time and memory complexity concerning system size and formula length.
• Successfully planned tasks for over 400 agents and formulas exceeding 400 in length, significantly outperforming existing methods.
• Demonstrated the method's efficacy on large fleets of service robots in simulation and hardware.

Conclusions:

• The proposed adaptive planning method offers a scalable and efficient solution for complex multi-agent task planning.
• It provides a verifiable framework for tasks with linear temporal logic requirements, even for large-scale systems.
• The approach enables robust coordination and planning in dynamic environments for real-world applications.