FMAP

FMAP is the current version of the Cooperative MAP system. FMAP builds upon MAP-POP, applying the same refinement planning search procedure and the privacy model. FMAP solves the main limitations of MAP-POP: it performs a complete search of the plan space and it applies an effective state-based heuristic function, which improves noticeably the performance of the system.

FMAP agents use an embedded forward-chaining POP to build refinement plans. This component makes possible to perform a complete search of the tree. Moreover, since refinement plans are built in a forward-chaining fashion, now it is possible to infer the frontier state of the plans, which leads to the application of powerful state-based heuristic functions.

We developed a heuristic function that counts the number of actions of a relaxed plan built between the frontier state of the refinement plan at hand and the goal state. The function is based on the notion of Domain Transition Graph, which reduces the cost of building a relaxed plan in a multi-agent context with privacy.

The FMAP system is integrated in the planInteraction multi-agent platform.

Improving heuristic estimates via multi-agent landmarks

The DTG-based heuristic function builds a relaxed plan by attaining the task goals one by one. A very efficient way to improve the quality of the estimates provided by the function is to sort the task goals according to the reasonable orderings among them.

The reasonable orderings are easily infered from the task's landmark graph, which also includes the landmarks and necessary orderings among them. We designed a multi-agent distributed version of the landmark extraction algorithm with builds the landmark graph while keeping the privacy of the agent's data.

The version of FMAP integrated in the planInteraction platform features a preliminary implementation of the landmark extraction algorithm.

Alejandro Torreño, Eva Onaindia, Óscar Sapena
FMAP: Distributed Cooperative Multi-Agent Planning
Applied Intelligence, (In Press), (2014)

Alejandro Torreño, Eva Onaindia, Óscar Sapena
FMAP: A Heuristic Approach to Cooperative Multi-Agent Planning
Preprints of the ICAPS'13 DMAP Workshop on Distributed and Multi-Agent Planning, pp. 84-92, (2013)