Performance analysis of bid calculation methods in multirobot market-based task allocation

In this study, the empirical results of a market-based task allocation method for heterogeneous and homogeneous robot teams and different types of tasks in 2 different environments are presented. The proposed method allocates robots to tasks through a parallel multiitem auction-based process. The main contribution of the proposed method is energy-based bid calculations, which take into account both the heterogeneity of the robot team and features of the tasks. The multirobot task allocation problem is considered as the optimal assignment problem and the Hungarian algorithm is used to clear the auctions. Simulations are carried out using energy-based, distance-based, and time-based bid calculation methods. The methods are implemented using a 3-type task set: cleaning a space, carrying an object, and monitoring. The tasks may have different sensitivities and/or priority levels. Simulations show that robot-task allocations of all of the methods result in similar utility values when single-type and/or same-featured tasks are used. However, for different-type and/or different-featured tasks, the proposed energy-based bid calculation method assigns a greater number of high-sensitivity tasks compared to the other 2 methods while consuming almost the same amount of energy in both environments. Additionally, the energy-based method has a filtering behavior for high-priority tasks. These properties of the proposed method increase the efficiency of the robot team.

Anahtar Kelimeler:

Multirobot, task allocation, market-based, optimal assignment, Hungarian algorithm, bid calculation, energy efficient, heterogeneous robot team

Performance analysis of bid calculation methods in multirobot market-based task allocation

Keywords:

Multirobot, task allocation, market-based, optimal assignment, Hungarian algorithm, bid calculation, energy efficient, heterogeneous robot team,

PDF

___

B.P. Gerkey, M.J. Matari´c, “A formal analysis and taxonomy of task allocation in multi-robot systems”, International Journal of Robotics Research, Vol. 23, pp. 939–954, 2004.
R.M. Zlot, A. Stentz, M.B. Dias, S. Thayer, “Multi-robot exploration controlled by a market economy”, Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3016–3023, 2002.
C. Tovey, M. Lagoudakis, S. Jain, S. Koenig, “The generation of bidding rules for auction-based robot coordination”, Proceedings of the 3rd International Multi-Robot Systems Workshop, pp. 3–14, 2005.
M.B. Dias, B. Ghanem, A. Stentz, “Improving cost estimation in market-based coordination of a distributed sensing task”, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3972–3977, 200
E.G. Jones, M.B. Dias, A. Stentz, “Learning-enhanced market-based task allocation for disaster response”, Technical Report CMU-RI-TR-06-48, Carnegie Mellon University, 2006.
E.G. Jones, M.B. Dias, A. Stentz, “Learning-enhanced market-based task allocation for oversubscribe domains”, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2308–2313, 2007. H. Hanna, “Decentralized approach for multi-robot task allocation problem with uncertain task execution”, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 535–540, 2005.
A. Viguria, A. Howard, “An integrated approach for achieving multirobot task formations”, IEEE/ASME Transactions on Mechatronics, Vol. 14, pp. 176–186, 2009.
M.B. Dias, R.M. Zlot, N. Kalra, A. Stentz, “Market-based multirobot coordination: a survey and analysis”, Proceedings of the IEEE, Vol. 94, pp. 1257–1270, 2006.
A.R. Mosteo, L. Montano, “Comparative experiments on optimization criteria and algorithms for auction based multi-robot task allocation”, Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3345–3350, 2007.
A. Ekici, P. Keskinocak, S. Koenig, “Multi-robot routing with linear decreasing rewards over time”, Proceedings of the IEEE International Conference on Robotics and Automation, pp. 958–963, 2009.
B. Kaleci, O. Parlaktuna, M. ¨ Ozkan, G. Kirlik, “Market-based task allocation by using assignment problem”, Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, pp. 135–141, 2010.
R.G. Smith, “The contract net protocol: high-level communication and control in a distributed problem solver”, IEEE Transactions on Computers, Vol. C-29, pp. 1104–1113, 1980.
S.C. Botelho, R. Alami, “M + : a scheme for multi-robot cooperation through negotiated task allocation and achievement”, Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 2, pp. 1234– 1239, 1999.
M. Golfarelli, D. Maio, S. Rizzi, “A task-swap negotiation protocol based on the contract net paradigm”, Report CSITE, No. 005-97, 1997.
T. Sandholm, “An implementation of the contract net protocol based on marginal cost calculations”, Proceedings of the 11th National Conference on Artiﬁcial Intelligence, pp. 256–262, 1993.
B.P. Gerkey, M.J. Matari´c, “Sold!: auction methods for multi-robot coordination”, IEEE Transactions on Robotics and Automation, Vol. 18, pp. 758–768, 2002.
R.G. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, H.L.S. Younes, “Coordination for multirobot exploration and mapping”, Proceedings of the National Conference on Artiﬁcial Intelligence, pp. 852–858, 2000.
S. Koenig, C. Tovey, M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, A. Meyerson, S. Jain, “The power of sequential single-item auctions for agent coordination”, Proceedings of the 21st National Conference on Artiﬁcial Intelligence, Vol. 2, pp. 1625–1629, 2006.
B.P. Gerkey, M.J. Matari´c, “A market-based formulation of sensor-actuator network coordination”, Technical Report SS-02-04, AAAI, 2002.
M. Nanjanath, M. Gini, “Repeated auctions for robust task execution by a robot team”, Robotics and Autonomous Systems, Vol. 58, pp. 900–909, 2010.
T. Sandholm, “Algorithm for optimal winner determination in combinatorial auctions”, Artiﬁcial Intelligence, Vol. 135, pp. 1–54, 2002.
M. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, S. Koenig, C. Tovey, A. Meyerson, S. Jain, “Auction-based multi-robot routing”, Proceedings of the International Conference on Robotics: Science and Systems, pp. 343–350, 2005.
M. Berhault, H. Huang, P. Keskinocak, S. Koenig, W. Elmaghraby, P. Griﬃn, A. Kleywegt, “Robot exploration with combinatorial auctions”, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. 2, pp. 1957–1962, 2003.
S. Sariel Talay, T. Balch, “A distributed multi-robot cooperation framework for real time task achievement”, Distributed Autonomous Robotic Systems, Vol. 7, pp. 187–196, 2006.
J. Melvin, P. Keskinocak, S. Koenig, C. Tovey, B.Y. Ozkaya, “Multi-robot routing with rewards and disjoint time windows”, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2332– 2337, 2007.
J. Munkres, “Algorithms for the assignment and transportation problems”, Journal of the Society for Industrial and Applied Mathematics, Vol. 5, pp. 32–38, 1957.
L.A. Wolsey, “Integer Programming”, New York, Wiley-Interscience, 1998.
H.W. Kuhn, “The Hungarian method for the assignment problem”, Naval Research Logistics Quarterly, Vol. 2, pp. 83–97, 1955.
D. Jungnickel, Graphs, Networks, and Algorithms, Berlin, Springer-Verlag, 1999.
M.S. Bazaara, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows, New York, Wiley, 1990.
Y. Mei, Y.H. Lu, Y.C. Hu, C.S.G. Lee, “Deployment of mobile robots with energy and timing constraints”, IEEE Transactions on Robotics, Vol. 22, pp. 507–522, 2006.
Oﬃcial web site for the SICK LMS 200 laser rangeﬁnder, https://www.mysick.com/eCat.aspx?go = FinderSearch&Cat = Gus&At = Fa&Cult = English&FamilyID= 344& Category= Produktﬁnder&Selections = 34243, 2010.
Oﬃcial web site for the CANON CV-C4 PTZ camera, http://www.usa.canon.com/consumer/controller?act = ModelInfoAct&tabact = ModelTechSpecsTabAct& fcategoryid= 262&modelid= 7402, 2010.
Oﬃcial web site for the gripper, http://www.activrobots.com/ACCESSORIES/gripper.html, 2010.