TASK ALLOCATION IN MARKET-BASED APPLICATIONS BY THE NEAREST NEIGHBOR HEURISTIC
Abstract
One of the main subjects that is studied in multi-robot applications is allocating tasks to robots and constructing objective-efficient tours for the robots using these allocated tasks. The main purpose of this paper is to allocate tasks via market-based task allocation architecture and to construct collision-free routes for multi-robot systems in a known indoor environment. For task allocation, a market-based architecture is constructed and applied to an example of a team of four heterogeneous mobile robots. In the study, tasks are allocated according to one of two constraints: minimizing the makespan of the robots and maximizing the robot task matching value of each robot in the group. These constraints are achieved by changing the value of a decision parameter. To show the effectiveness of the proposed method, comparisons are made within these constraints. To construct path, a combination of the Nearest Neighbor heuristic and Dijkstra's shortest path algorithms is used. To construct non-conflicting paths, a method that detects and solves collisions is developed. In the study, for agent communication Open Agent Architecture is used. Additionally, simulations on the MobileSim platform are conducted to verify the feasibility of the proposed method.
Keywords
Multi-agent, Task allocation, Market-based, Path planning, Collision avoidance
References
- Brumitt B. and Stenz A. (1998). Grammps: a Generalized Mission Planner for Multiple Mobile Robots. In Proceedings of the IEEE International Conference on Robotics and Automation.
- Caloud P., Choi W., Latombe J., Pape C. Le, And Yim M. (1990). Indoor Automation with Many Mobile Robots. In Proceedings of the IEEE International Workshop on Intelligent Robotics and Systems (IROS).
- Cheyer A., and Martin D. (2001). The Open Agent Architecture. Journal of Autonomous Agents and Multi-Agent Systems, vol. 4, no. 1, 143-148.
- Dias M. B. and Stenz A. (2002). Opportunistic Optimization for Market-based Multirobot Control. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems 2714–2720.
- Dijkstra E.W. (1959). A Note on Two Problems in Connexion with Graphs. Numerische Mathematik. Volume 1, Issue 1, 269-271.
- Gerkey B.P. and Mataric M.J. (2000). Murdoch: Publish/Subscribe Task Allocation for Heterogeneous Agents. In Proceedings of the Fourth International Conference on Autonomous Agents. 203–204.
- Guo Y. and Parker L. E. (2002). A Distributed and Optimal Motion Planning Approach for Multiple Mobile Robots. In Proceedings of IEEE International Conference on Robotics & Automation Washington DC 2612-2619.
- Gurel U.,Adar N, Parlaktuna O. (2013). Priority
- based Task Allocation in Auction-based
- Symposium , 19-21 June 2013 , Albena Bulgaria.