@inproceedings {icaps16-158,
    track    = {​​Robotics Track},
    title    = {Multi-Agent Path Finding with Kinematic Constraints},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183},
    author   = {Wolfgang Hoenig and  T. K. Satish Kumar and  Liron Cohen and  Hang Ma and  Hong Xu and  Nora Ayanian and  Sven Koenig},
    abstract = {Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. 
Given a discretized environment and a set of agents with assigned start 
and goal locations, modern solvers can quickly find conflict-free paths 
with a user-defined sub-optimality guarantee. However, these approaches 
make simplifying assumptions that ignore the kinematic constraints - in 
real life, robots are constrained by their kinematics such as maximum 
velocities and suffer from imperfect plan execution. This unfortunately 
prevents the direct use of powerful MAPF solvers developed in the AI 
community. In this paper, we introduce a novel algorithm which 
postprocesses the output of a MAPF solver to create schedules that can 
be executed on real robots. The schedules produced by our algorithm work 
on non-holonomic robots, allow for kinematic constraints, provide a 
guaranteed safety distance between any two robots, and exploit slack 
which can be used to avoid costly replanning. Our approach uses the 
algorithmic framework of simple temporal problems that are well studied 
for their simplicity and tractability. We evaluate our approach in 
simulation as well as on real differential-drive robots, showcasing how 
the resulting plan obeys the kinematic constraints.},
    keywords = {planning and coordination methods for multiple robots,robot motion; path; task and mission planning and execution,real-world planning applications for autonomous robots}
}

{"_id":"YsujdxixJYW9kEX3W","bibbaseid":"hoenig-kumar-cohen-ma-xu-ayanian-koenig-multiagentpathfindingwithkinematicconstraints","downloads":0,"creationDate":"2016-06-09T01:21:35.074Z","title":"Multi-Agent Path Finding with Kinematic Constraints","author_short":["Hoenig, W.","Kumar, T. K. S.","Cohen, L.","Ma, H.","Xu, H.","Ayanian, N.","Koenig, S."],"year":null,"bibtype":"inproceedings","biburl":"icaps16.icaps-conference.org/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","track":"​​Robotics Track","title":"Multi-Agent Path Finding with Kinematic Constraints","url":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183","author":[{"firstnames":["Wolfgang"],"propositions":[],"lastnames":["Hoenig"],"suffixes":[]},{"firstnames":["T.","K.","Satish"],"propositions":[],"lastnames":["Kumar"],"suffixes":[]},{"firstnames":["Liron"],"propositions":[],"lastnames":["Cohen"],"suffixes":[]},{"firstnames":["Hang"],"propositions":[],"lastnames":["Ma"],"suffixes":[]},{"firstnames":["Hong"],"propositions":[],"lastnames":["Xu"],"suffixes":[]},{"firstnames":["Nora"],"propositions":[],"lastnames":["Ayanian"],"suffixes":[]},{"firstnames":["Sven"],"propositions":[],"lastnames":["Koenig"],"suffixes":[]}],"abstract":"Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and a set of agents with assigned start and goal locations, modern solvers can quickly find conflict-free paths with a user-defined sub-optimality guarantee. However, these approaches make simplifying assumptions that ignore the kinematic constraints - in real life, robots are constrained by their kinematics such as maximum velocities and suffer from imperfect plan execution. This unfortunately prevents the direct use of powerful MAPF solvers developed in the AI community. In this paper, we introduce a novel algorithm which postprocesses the output of a MAPF solver to create schedules that can be executed on real robots. The schedules produced by our algorithm work on non-holonomic robots, allow for kinematic constraints, provide a guaranteed safety distance between any two robots, and exploit slack which can be used to avoid costly replanning. Our approach uses the algorithmic framework of simple temporal problems that are well studied for their simplicity and tractability. We evaluate our approach in simulation as well as on real differential-drive robots, showcasing how the resulting plan obeys the kinematic constraints.","keywords":"planning and coordination methods for multiple robots,robot motion; path; task and mission planning and execution,real-world planning applications for autonomous robots","bibtex":"@inproceedings {icaps16-158,\r\n track = {​​Robotics Track},\r\n title = {Multi-Agent Path Finding with Kinematic Constraints},\r\n url = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183},\r\n author = {Wolfgang Hoenig and T. K. Satish Kumar and Liron Cohen and Hang Ma and Hong Xu and Nora Ayanian and Sven Koenig},\r\n abstract = {Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. \r\nGiven a discretized environment and a set of agents with assigned start \r\nand goal locations, modern solvers can quickly find conflict-free paths \r\nwith a user-defined sub-optimality guarantee. However, these approaches \r\nmake simplifying assumptions that ignore the kinematic constraints - in \r\nreal life, robots are constrained by their kinematics such as maximum \r\nvelocities and suffer from imperfect plan execution. This unfortunately \r\nprevents the direct use of powerful MAPF solvers developed in the AI \r\ncommunity. In this paper, we introduce a novel algorithm which \r\npostprocesses the output of a MAPF solver to create schedules that can \r\nbe executed on real robots. The schedules produced by our algorithm work \r\non non-holonomic robots, allow for kinematic constraints, provide a \r\nguaranteed safety distance between any two robots, and exploit slack \r\nwhich can be used to avoid costly replanning. Our approach uses the \r\nalgorithmic framework of simple temporal problems that are well studied \r\nfor their simplicity and tractability. We evaluate our approach in \r\nsimulation as well as on real differential-drive robots, showcasing how \r\nthe resulting plan obeys the kinematic constraints.},\r\n keywords = {planning and coordination methods for multiple robots,robot motion; path; task and mission planning and execution,real-world planning applications for autonomous robots}\r\n}\r\n\r\n","author_short":["Hoenig, W.","Kumar, T. K. S.","Cohen, L.","Ma, H.","Xu, H.","Ayanian, N.","Koenig, S."],"key":"icaps16-158","id":"icaps16-158","bibbaseid":"hoenig-kumar-cohen-ma-xu-ayanian-koenig-multiagentpathfindingwithkinematicconstraints","role":"author","urls":{"Paper":"http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13183"},"keyword":["planning and coordination methods for multiple robots","robot motion; path; task and mission planning and execution","real-world planning applications for autonomous robots"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"search_terms":["multi","agent","path","finding","kinematic","constraints","hoenig","kumar","cohen","ma","xu","ayanian","koenig"],"keywords":["planning and coordination methods for multiple robots","robot motion; path; task and mission planning and execution","real-world planning applications for autonomous robots"],"authorIDs":[],"dataSources":["iMkx859KiXcegwsin","EZtZjCTnxcdTTyeij"]}