Distributed Optimal Planning, An Approach by Weighted Automata Calculus

We consider a distributed system modeled as a possibly large network of automata. Planning in this system consists in selecting and organizing actions in order to reach a goal state in an optimal manner, assuming actions have a cost. To cope with the complexity of the system, we propose a distributed/modular planning approach. In each automaton or component, an agent explores local action plans that reach the local goal. The agents have to coordinate their search in order to select local plans that (1) can be assembled into a valid global plan and (2) ensure the optimality of this global plan. The proposed solution takes the form of a message passing algorithm, of peer-to-peer nature: no coordinator is needed. We show that local plan selections can be performed by combining operations on weighted languages, and then propose a more practical implementation in terms of weighted automata calculus.
Eric Fabre is research scientist at INRIA, the French National Research Institute in Computer Science, in the DistribCom team. The team is working on formal models for distributed systems and on distributed algorithms to monitor such systems (state estimation, diagnosis, control, etc.). The team has two main application areas : Web Services, and Autonomic Telecommunication Network Management. Eric Fabre's background is in signal processing, digital telecommunications, and information theory. His current interests are now in distributed algorithms to manage disributed systems. He is co-head of a joint research team with Bell Labs France dedicated to the design of self-managed telecommunication networks.