  This paper presents a solution to the automatic task planning problem for
multi-agent systems. A formal framework is developed based on the
Nondeterministic Finite Automata with $\epsilon$-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 cycle
for solving other scenarios, while allowing the incorporation of failure modes
on-the-fly. Two case studies are provided: a simple one to showcase the
concepts of the proposed methodology and a more elaborate one to demonstrate
the effectiveness and validity of the methodology.
