TASK ALLOCATION IN MARKET-BASED APPLICATIONS BY THE NEAREST NEIGHBOR HEURISTIC

Year 2013, Volume: 14 Issue: 2, 173 - 182, 11.11.2013

Uğur Gürel , Osman Parlaktuna , Nihat Adar , Selçuk Canbek

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

EN YAKIN KOMŞU SEZGİSELİ YAKLAŞIMI İLE MARKET TABANLI GÖREV DAĞITIMI

Abstract

Keywords

Çok-erkinli, Görev dağıtımı, Market tabanlı, Yol planlaması, Çarpışmadan kaçınma

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.
• Guzzoni D., Cheyer A. , Julia L., and Konolige Kurt. (1997). Many Robots Make Short Work Report of The Sri International Mobile Robot Team. AI Magazine Volume 18 Number 1 55-64.
• Hasgul S., Saricicek İ., Ozkan M., Parlaktuna O. (2009). Project-oriented Task Scheduling for Mobile Robot Team. Journal of Intelligent Manufacturing, Volume 20, Issue 2, 151-158.
• Adept MobileRobots. http://www.mobilerobots.com/Software/M obileSim.aspx.
• Accessed at 15.10.2013 .
• Hu Y., Wang L., Liang J., Wang T. (2011). Cooperative Box-pushing with Multiple Autonomous Robotic Fish in Underwater Environment. Applications, IET Volume: 5 Issue: 17 2015 – 2022.
• Kaleci B., Parlaktuna O., and Ozkan M. (2010). Market-based Task Allocation Method using Exploratory Learning for Heterogeneous Multi-robot Team. International Symposium on Innovations in Intelligent Systems and Applications (INISTA 2010). Kayseri, Turkey.
• Khamis A. M., Elmogy A. M., Karray F. O. (2011). Complex Task Allocation in Mobile Surveillance Systems. Journal of Intelligent & Robotic Systems. Volume 64, Issue 1 33-55.
• Ko J., Stewart B., Fox D., Konolige K. and Limketkai B. (2003). A Practical Decision-Theoretic Approach to Multi- robot Mapping and Exploration. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems. 2714–2720.
• Laporte G. (1992). The Vehicle Routing Problem: an Overview of Exact and Approximate Algorithms. European Journal of Operational Research. Vol 59 345-358.
• Ling X., Stentz, A. (2011). Market-based Coordination of Coupled Robot Systems. Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference. 2784 – 2789.
• Ostergaard, E.H., Mataric, M.J., Sukhatme, G. (2001). Distributed Multi-robot Task Allocation for Emergency Handling. G.S.Intelligent Robots and Systems, Proceedings. IEEE/RSJ International Conference on Volume: 2 821 - 826.
• Parker L. E. (1998). Alliance: An Architecture for Fault-tolerant Multi-robot Cooperation. IEEE Transactions on Robotics and Automation. 14(2) 220–240
• Parlaktuna O., Sipahioglu A., Yazıcı A. (2007). A Vrp-based Route Planning for A Mobile Robot Group. Turk. Journal Electric Engineering. 15 187-197
• Sandholm T. (1993). An Implementation of The Contract Net Protocol based on Marginal Cost Calculations. In Proceedings of the 12th International Workshop on Distributed Artificial Intelligence. 256-262
• Sariel S. and Balch T.R. (2006). Efficient Bids on Task Allocation for Multi-robot Exploration. In Proc FLAIRS Conference. 116-121.
• Yu Z., Jinhai L., Guochang G., Rubo Z. and Haiyan Y., (2002). An Implementation of Evolutionary Computation for Path Planning of Cooperative Mobile Robots. In Proc 4"' World Congress on Intelligent Control and Automation. 1798-1802
• Zu L., Tian Y. and Liu J. (2004). Algorithms of Task-allocation and Cooperation in Multi Mobile Robot System. In Proc 5" World Congress on Intelligent Control and Automation, Hangzhou, P.R. China. 2841- 2845.