A Formal Framework for Multi-Agent Task Planning
Journal
IEEE Transactions on Automatic Control
Date Issued
August 22, 2025
Author(s)
DOI
10.1109/TAC.2025.3601769
Abstract
This paper presents a solution to the task planning problem for multi-agent systems. A formal framework is developed based on the Nondeterministic Finite Automata with ϵ-transitions, where given the capabilities, constraints and failure modes of the agents involved, an initial state of the system and a task specification, an optimal solution is generated that satisfies the system constraints and the task specification. The resulting solution is guaranteed to be complete and optimal; moreover, a heuristic solution that offers significant reduction of the computational requirements while relaxing the completeness and optimality requirements is proposed. The constructed system model is independent from the initial condition and the task specification, alleviating the need to repeat the costly pre-processing step for solving other scenarios, while allowing the incorporation of failure modes on-the-fly. An analysis of the completeness and optimality properties as well as the class of addressable problems is provided.
File(s)![Thumbnail Image]()
Name
A_Formal_Framework.pdf
Size
545.22 KB
Format
Adobe PDF
Checksum (MD5)
9ed88ba0ef02c33e7d1021e38a9a87a3