Potential Heuristics for Multi-Agent Planning. Štolba, M., Fišer, D., & Komenda, A. In
Potential Heuristics for Multi-Agent Planning [link]Paper  abstract   bibtex   
Distributed heuristic search is a well established technique for multi-agent planning. It has been shown that distributed heuristics may crucially improve the search guidance, but are costly in terms of communication and computation time. One solution is to compute a heuristic additively, in the sense that each agent can compute its part of the heuristic independently and obtain a complete heuristic estimate by summing up the individual parts. In this paper, we show that the recently published potential heuristic is a good candidate for such heuristic, moreover admissible. We also demonstrate how the multi-agent distributed A* search can be modified in order to benefit from such additive heuristic. The modified search equipped with a distributed potential heuristic outperforms the state of the art.
@inproceedings {icaps16-99,
    track    = {​Main Track},
    title    = {Potential Heuristics for Multi-Agent Planning},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13117},
    author   = {Michal Štolba and  Daniel Fišer and  Antonín Komenda},
    abstract = {Distributed heuristic search is a well established technique for multi-agent planning. It has been shown that distributed heuristics may crucially improve the search guidance, but are costly in terms of communication and computation time. One solution is to compute a heuristic additively, in the sense that each agent can compute its part of the heuristic independently and obtain a complete heuristic estimate by summing up the individual parts. In this paper, we show that the recently published potential heuristic is a good candidate for such heuristic, moreover admissible. We also demonstrate how the multi-agent distributed A* search can be modified in order to benefit from such additive heuristic. The modified search equipped with a distributed potential heuristic outperforms the state of the art.},
    keywords = {Distributed and multi-agent planning}
}
Downloads: 0