Networks of automata with read arcs: a tool for distributed planning

摘要

A planning problem consists in driving a system from its current state to a set of target states. Problems are generally expressed by a collection of state variables, and actions that change the value of a subset of these variables. Such problems can be modeled as networks of automata, one per state variable, that partially synchronize on some actions. Distributed planning (or factored planning) consists in driving each of these automata to its goal state(s), while preserving the coherence of their interactions. Real planning problems, however, need to model actions that can only be performed in one component when another component is in a specific state. This paper proposes a mechanism to capture this phenomenon, under the form of automata with read arcs, reproducing what already exists for Petri nets. It is shown that a previous approach to distributed planning, based on automata computations, can be extended to this new setting.