TY - GEN
T1 - Multirobot task allocation with real-time path planning
AU - Woosley, Bradley
AU - Dasgupta, Prithviraj
PY - 2013
Y1 - 2013
N2 - We consider the multi-robot task allocation (MRTA) problem in an initially unknown environment. The objective of the MRTA problem is to find a schedule or sequence of tasks that should be performed by a set of robots so that the cost or energy expended by the robots is minimized. Existing solutions for the MRTA problem mainly concentrate on finding an efficient task allocation among robots, without directly incorporating changes to tasks' costs originating from changes in robots' paths due to dynamically detected obstacles while moving between tasks. Dynamically updating path costs is an important aspect as changing path costs can alter the task sequence for robots that corresponds to the minimum cost. In this paper, we attempt to address this problem by developing an algorithm called MRTA-RTPP (MRTA with Real-time Path Planning) by integrating a greedy MRTA algorithm for task planning with a Field D*-based path planning algorithm. Our technique is capable of handling dynamic changes in a robot's path costs due to static as well as mobile obstacles and computes a new task schedule if the original schedule is no longer optimal due to the robots' replanned paths. We have verified our proposed technique on physical Corobot robots that perform surveillance-like tasks by visiting a set of locations. Our experimental results show that that our MRTA technique is able to handle dynamic path changes while reducing the cost of the schedule to the robots.
AB - We consider the multi-robot task allocation (MRTA) problem in an initially unknown environment. The objective of the MRTA problem is to find a schedule or sequence of tasks that should be performed by a set of robots so that the cost or energy expended by the robots is minimized. Existing solutions for the MRTA problem mainly concentrate on finding an efficient task allocation among robots, without directly incorporating changes to tasks' costs originating from changes in robots' paths due to dynamically detected obstacles while moving between tasks. Dynamically updating path costs is an important aspect as changing path costs can alter the task sequence for robots that corresponds to the minimum cost. In this paper, we attempt to address this problem by developing an algorithm called MRTA-RTPP (MRTA with Real-time Path Planning) by integrating a greedy MRTA algorithm for task planning with a Field D*-based path planning algorithm. Our technique is capable of handling dynamic changes in a robot's path costs due to static as well as mobile obstacles and computes a new task schedule if the original schedule is no longer optimal due to the robots' replanned paths. We have verified our proposed technique on physical Corobot robots that perform surveillance-like tasks by visiting a set of locations. Our experimental results show that that our MRTA technique is able to handle dynamic path changes while reducing the cost of the schedule to the robots.
UR - http://www.scopus.com/inward/record.url?scp=84889853891&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84889853891&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84889853891
SN - 9781577356059
T3 - FLAIRS 2013 - Proceedings of the 26th International Florida Artificial Intelligence Research Society Conference
SP - 574
EP - 579
BT - FLAIRS 2013 - Proceedings of the 26th International Florida Artificial Intelligence Research Society Conference
T2 - 26th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2013
Y2 - 22 May 2013 through 24 May 2013
ER -