Skip to Main content Skip to Navigation
Reports

A-sharp: a Distributed A-star for Factored Planning

Loïg Jezequel 1 Eric Fabre 1 
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Factored planning consists in driving a modular or distributed system to a target state, in an optimal manner, assuming all actions are controllable. Such problems take the form of path search in a product of graphs. The state space of each component is a graph, in which one must find a path to the local goal of this component. But when all components are considered jointly, the problem amounts to finding a path in each of these state graphs, while ensuring their compatibility on the actions that must be performed jointly by some components of the system. This paper proposes a solution under the form of a multi-agent version of A*. The proposed A# assembles several A*, each one performing a biased depth-first search in the graph of each component, and coordinates their exchanges to quickly find compatible paths to the goal.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-00687434
Contributor : Loïg Jezequel Connect in order to contact the contributor
Submitted on : Friday, July 13, 2012 - 7:00:18 AM
Last modification on : Tuesday, March 8, 2022 - 11:50:02 AM
Long-term archiving on: : Wednesday, December 14, 2016 - 10:40:10 PM

File

RR-7927.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00687434, version 1

Citation

Loïg Jezequel, Eric Fabre. A-sharp: a Distributed A-star for Factored Planning. [Research Report] RR-7927, INRIA. 2012. ⟨hal-00687434⟩

Share

Metrics

Record views

273

Files downloads

207