@INPROCEEDINGS{JSvan17b,
 AUTHOR= "J. Svancara and P. Surynek",
 TITLE= "New Flow-based Heuristic for Search Algorithms Solving Multi-Agent Path Finding",
 BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)",
 PAGES= "451--458",
 YEAR= "2017",
 PDF= "http://svancara.net/files/ICAART_2017_46_CR.pdf",
 FLAGS= ":2017:,:jirisvancara:,:pavelsurynek:",
 ABSTRACT= 
"We address the problem of optimal multi-agent path finding (MAPF) in this
paper. The task is to find a set of actions for each agent in know terrain so
that each agent arrives to its desired destination from a given starting
position. Agents are not allowed to collide with each other along their
paths. Furthermore, a solution that minimizes the total time is required. In
this paper we study search-based algorithms that systematically explore state
space. These algorithms require a good heuristic function that can improve the
computational effectiveness by changing the order in which the states are
expanded. We propose such new heuristic, which is based on relaxation of MAPF
solving via its reduction to multi-commodity flow over time expanded graph.
The multi-commodity flow is relaxed to single commodity flow, which can be
solved in polynomial time.  We show that our new heuristic is monotone and
therefore can be used in search-based algorithms effectively.  We also give
theoretical analysis of the new heuristic and compare it experimentally with
base-line heuristics that are often used."
}

{"_id":"TSLmHGJXAyGBw7Dik","bibbaseid":"svancara-surynek-newflowbasedheuristicforsearchalgorithmssolvingmultiagentpathfinding-2017","authorIDs":[],"author_short":["Svancara, J.","Surynek, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["J."],"propositions":[],"lastnames":["Svancara"],"suffixes":[]},{"firstnames":["P."],"propositions":[],"lastnames":["Surynek"],"suffixes":[]}],"title":"New Flow-based Heuristic for Search Algorithms Solving Multi-Agent Path Finding","booktitle":"Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)","pages":"451–458","year":"2017","pdf":"http://svancara.net/files/ICAART_2017_46_CR.pdf","flags":":2017:,:jirisvancara:,:pavelsurynek:","abstract":"We address the problem of optimal multi-agent path finding (MAPF) in this paper. The task is to find a set of actions for each agent in know terrain so that each agent arrives to its desired destination from a given starting position. Agents are not allowed to collide with each other along their paths. Furthermore, a solution that minimizes the total time is required. In this paper we study search-based algorithms that systematically explore state space. These algorithms require a good heuristic function that can improve the computational effectiveness by changing the order in which the states are expanded. We propose such new heuristic, which is based on relaxation of MAPF solving via its reduction to multi-commodity flow over time expanded graph. The multi-commodity flow is relaxed to single commodity flow, which can be solved in polynomial time. We show that our new heuristic is monotone and therefore can be used in search-based algorithms effectively. We also give theoretical analysis of the new heuristic and compare it experimentally with base-line heuristics that are often used.","bibtex":"@INPROCEEDINGS{JSvan17b,\n AUTHOR= \"J. Svancara and P. Surynek\",\n TITLE= \"New Flow-based Heuristic for Search Algorithms Solving Multi-Agent Path Finding\",\n BOOKTITLE= \"Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)\",\n PAGES= \"451--458\",\n YEAR= \"2017\",\n PDF= \"http://svancara.net/files/ICAART_2017_46_CR.pdf\",\n FLAGS= \":2017:,:jirisvancara:,:pavelsurynek:\",\n ABSTRACT= \n\"We address the problem of optimal multi-agent path finding (MAPF) in this\npaper. The task is to find a set of actions for each agent in know terrain so\nthat each agent arrives to its desired destination from a given starting\nposition. Agents are not allowed to collide with each other along their\npaths. Furthermore, a solution that minimizes the total time is required. In\nthis paper we study search-based algorithms that systematically explore state\nspace. These algorithms require a good heuristic function that can improve the\ncomputational effectiveness by changing the order in which the states are\nexpanded. We propose such new heuristic, which is based on relaxation of MAPF\nsolving via its reduction to multi-commodity flow over time expanded graph.\nThe multi-commodity flow is relaxed to single commodity flow, which can be\nsolved in polynomial time. We show that our new heuristic is monotone and\ntherefore can be used in search-based algorithms effectively. We also give\ntheoretical analysis of the new heuristic and compare it experimentally with\nbase-line heuristics that are often used.\"\n}\n\n","author_short":["Svancara, J.","Surynek, P."],"key":"JSvan17b","id":"JSvan17b","bibbaseid":"svancara-surynek-newflowbasedheuristicforsearchalgorithmssolvingmultiagentpathfinding-2017","role":"author","urls":{},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://mapf.info/bib/mapf.bib","creationDate":"2019-05-05T18:02:17.732Z","downloads":0,"keywords":[],"search_terms":["new","flow","based","heuristic","search","algorithms","solving","multi","agent","path","finding","svancara","surynek"],"title":"New Flow-based Heuristic for Search Algorithms Solving Multi-Agent Path Finding","year":2017,"dataSources":["oEkRzPPMbrG9LyYPh"]}