Potential Heuristics for Multi-Agent Planning

Potential Heuristics for Multi-Agent Planning. Štolba, M., Fišer, D., & Komenda, A. In

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

{"_id":"nB7CHYSoD59aGbJjt","bibbaseid":"tolba-fier-komenda-potentialheuristicsformultiagentplanning","downloads":0,"creationDate":"2016-03-09T03:04:33.018Z","title":"Potential Heuristics for Multi-Agent Planning","author_short":["Štolba, M.","Fišer, D.","Komenda, A."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"Main Track","title":"Potential Heuristics for Multi-Agent Planning","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13117","author":[{"firstnames":["Michal"],"propositions":[],"lastnames":["Štolba"],"suffixes":[]},{"firstnames":["Daniel"],"propositions":[],"lastnames":["Fišer"],"suffixes":[]},{"firstnames":["Antonín"],"propositions":[],"lastnames":["Komenda"],"suffixes":[]}],"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","bibtex":"@inproceedings {icaps16-99,\r\n track = {Main Track},\r\n title = {Potential Heuristics for Multi-Agent Planning},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13117},\r\n author = {Michal Štolba and Daniel Fišer and Antonín Komenda},\r\n 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.},\r\n keywords = {Distributed and multi-agent planning}\r\n}\r\n","author_short":["Štolba, M.","Fišer, D.","Komenda, A."],"key":"icaps16-99","id":"icaps16-99","bibbaseid":"tolba-fier-komenda-potentialheuristicsformultiagentplanning","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13117"},"keyword":["Distributed and multi-agent planning"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"search_terms":["potential","heuristics","multi","agent","planning","štolba","fišer","komenda"],"keywords":["distributed and multi-agent planning"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}