Scheduling Models for Multi-Agent Path Finding

Scheduling Models for Multi-Agent Path Finding. Bartak, R., Svancara, J., & Vlk, M. In Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pages 189–200, 2017.
abstract bibtex

Multi-agent path finding (MAPF) deals with the problem of finding a collision free path for a set of agents. The agents are located at nodes of a directed graph, they can move over the arcs, and each agent has its own destination node. It is not possible for two agents to be at the same node at the same time. This paper suggests to model the MAPF problem using scheduling techniques, namely, nodes are seen as unary resources. We present three models of the problem. One model is motivated by network flows, another model uses classical unary resource constraints together with path constraints, and the last model works with optional activities. We compare the efficiency of models experimentally.

@INPROCEEDINGS{JSvan17a,
 AUTHOR= "R. Bartak and J. Svancara and M. Vlk",
 TITLE= "Scheduling Models for Multi-Agent Path Finding",
 BOOKTITLE= "Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA)",
 PAGES= "189--200",
 YEAR= "2017",
 PDF= "http://svancara.net/files/MISTA_2017_paper_44.pdf",
 FLAGS= ":2017:,:romanbartak:,:jirisvancara:,:marekvlk:",
 ABSTRACT= 
"Multi-agent path finding (MAPF) deals with the problem of finding a collision
free path for a set of agents. The agents are located at nodes of a directed
graph, they can move over the arcs, and each agent has its own destination
node. It is not possible for two agents to be at the same node at the same
time. This paper suggests to model the MAPF problem using scheduling
techniques, namely, nodes are seen as unary resources. We present three models
of the problem. One model is motivated by network flows, another model uses
classical unary resource constraints together with path constraints, and the
last model works with optional activities. We compare the efficiency of models
experimentally."  
}

Downloads: 0

{"_id":"6YTcf22bZmYyQRPWp","bibbaseid":"bartak-svancara-vlk-schedulingmodelsformultiagentpathfinding-2017","authorIDs":[],"author_short":["Bartak, R.","Svancara, J.","Vlk, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["R."],"propositions":[],"lastnames":["Bartak"],"suffixes":[]},{"firstnames":["J."],"propositions":[],"lastnames":["Svancara"],"suffixes":[]},{"firstnames":["M."],"propositions":[],"lastnames":["Vlk"],"suffixes":[]}],"title":"Scheduling Models for Multi-Agent Path Finding","booktitle":"Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA)","pages":"189–200","year":"2017","pdf":"http://svancara.net/files/MISTA_2017_paper_44.pdf","flags":":2017:,:romanbartak:,:jirisvancara:,:marekvlk:","abstract":"Multi-agent path finding (MAPF) deals with the problem of finding a collision free path for a set of agents. The agents are located at nodes of a directed graph, they can move over the arcs, and each agent has its own destination node. It is not possible for two agents to be at the same node at the same time. This paper suggests to model the MAPF problem using scheduling techniques, namely, nodes are seen as unary resources. We present three models of the problem. One model is motivated by network flows, another model uses classical unary resource constraints together with path constraints, and the last model works with optional activities. We compare the efficiency of models experimentally.","bibtex":"@INPROCEEDINGS{JSvan17a,\n AUTHOR= \"R. Bartak and J. Svancara and M. Vlk\",\n TITLE= \"Scheduling Models for Multi-Agent Path Finding\",\n BOOKTITLE= \"Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA)\",\n PAGES= \"189--200\",\n YEAR= \"2017\",\n PDF= \"http://svancara.net/files/MISTA_2017_paper_44.pdf\",\n FLAGS= \":2017:,:romanbartak:,:jirisvancara:,:marekvlk:\",\n ABSTRACT= \n\"Multi-agent path finding (MAPF) deals with the problem of finding a collision\nfree path for a set of agents. The agents are located at nodes of a directed\ngraph, they can move over the arcs, and each agent has its own destination\nnode. It is not possible for two agents to be at the same node at the same\ntime. This paper suggests to model the MAPF problem using scheduling\ntechniques, namely, nodes are seen as unary resources. We present three models\nof the problem. One model is motivated by network flows, another model uses\nclassical unary resource constraints together with path constraints, and the\nlast model works with optional activities. We compare the efficiency of models\nexperimentally.\" \n}\n\n","author_short":["Bartak, R.","Svancara, J.","Vlk, M."],"key":"JSvan17a","id":"JSvan17a","bibbaseid":"bartak-svancara-vlk-schedulingmodelsformultiagentpathfinding-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":["scheduling","models","multi","agent","path","finding","bartak","svancara","vlk"],"title":"Scheduling Models for Multi-Agent Path Finding","year":2017,"dataSources":["oEkRzPPMbrG9LyYPh"]}