MARKET-BASED MULTI-ROBOT TASK ALLOCATION USING ENERGY-BASED BID CALCULATIONS

Burak Kaleci and Osman Parlaktuna

References

  1. [1] B.P. Gerkey and M. Mataric, A formal analysis and taxonomy of task allocation in multi-robot systems, International Journal of Robotics Research, 23 (9), 2004, 939–954.
  2. [2] R.M. Zlot, A. Stentz, M.B. Dias, and S. Thayer, Multi-robot exploration controlled by a market economy, Proc. IEEE Int. Conf. on Robotics and Automation, Washington, DC, 2002, 3016–3023.
  3. [3] C. Tovey, M. Lagoudakis, S. Jain, and S. Koenig, The generation of bidding rules for auction-based robot coordination, in A. Schultz, L. Parker, and F. Schneider (eds.), Lecture Notes in Artificial Intelligence; Proceedings of the Third Int. Multi-Robot Systems Workshop (Washington, DC: Springer, 2005), 3–14.
  4. [4] M.B. Dias, B. Ghanem, and A. Stentz, Improving cost estimation in market-based coordination of a distributed sensing task, Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Alberta, Canada, 2005, 3972–3977.
  5. [5] E.G. Jones, M.B. Dias, and A. Stentz, Learning-enhanced market-based task allocation for disaster response, Technical Report CMU-RI-TR-06-48, Carnegie Mellon University, 2006.
  6. [6] E.G. Jones, M.B. Dias, and A. Stentz, Learning-enhanced market-based task allocation for oversubscribe domains, Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, San Diego, CA, 2007, 2308–2313.
  7. [7] H. Hanna, Decentralized approach for multi-robot task allocation problem with uncertain task execution, Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Alberta, Canada, 2005, 535–540.
  8. [8] A. Viguria and A. Howard, An integrated approach for achieving multirobot task formations, IEEE/ASME Transactions on Mechatronics, 14 (2), 2009, 176–186.
  9. [9] M.B. Dias, R.M. Zlot, N. Kalra, and A. Stentz, Market-based multirobot coordination: A survey and analysis, Proceedings of the IEEE, 94 (7), 2006, 1257–1270.
  10. [10] A.R. Mosteo and L. Montano, Comparative experiments on optimization criteria and algorithms for auction based multi-robot task allocation, Proc. IEEE Int. Conf. on Robotics and Automation, Roma, Italy, 2007, 3345–3350.
  11. [11] A. Ekici, P. Keskinocak, and S. Koenig, Multi-robot routing with linear decreasing rewards over time, Proc. IEEE Int. Conf. on Robotics and Automation, Kobe, Japan, 2009, 958–963.
  12. [12] B. Kaleci, O. Parlaktuna, M. Özkan, and G. Kirlik, Market-based task allocation by using assignment problem, Proc. IEEE Int. Conf. on Systems, Man and Cybernetics, Istanbul, Turkey, 2010, 135–141.
  13. [13] R. Smith, The contract net protocol: High-level communication and control in a distributed problem solver, IEEE Transactions on Computers, C-29 (12), 1980.
  14. [14] S.C. Botelho and R. Alami, M+: A scheme for multi-robot cooperation through negotiated task allocation and achievement, Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, 1999, 1234–1239.
  15. [15] M. Golfarelli, D. Maio, and S. Rizzi, A task-swap negotiation protocol based on the contract net paradigm, Report CSITE No. 005-97, 1997.
  16. [16] T. Sandholm, An implementation of the contract net protocol based on marginal cost calculations, Proc. National Conf. on Artificial Intelligence, 1993, 256–262.
  17. [17] B.P. Gerkey and M.J. Mataric, Sold!: Auction methods for multi-robot coordination, IEEE Transactions on Robotics and Automation, 18 (5), 2002, 758–768.
  18. [18] R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, and H. Younes, Coordination for multi-robot exploration and mapping, Proc. National Conf. on Artificial Intelligence, 2000, 852–858.
  19. [19] S. Koenig, C. Tovey, M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, A. Meyerson, and S. Jain. The power of sequential single-item auctions for agent coordination, Proc. of the Conf. on Artificial Intelligence, 2006, 1625–1629.
  20. [20] B.P. Gerkey and M.J. Mataric, A market-based formulation of sensor-actuator network coordination, Technical Report SS-02-04, AAAI, 2002.
  21. [21] M. Nanjanath and M. Gini, Repeated auctions for robust task execution by a robot team, Robotics and Autonomous Systems, 58 (7), 2010, 900–909.
  22. [22] T. Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence 135 (1), 2002, 1–54.
  23. [23] M. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, S. Koenig, C. Tovey, A. Meyerson, and S. Jain, Auction-based multi-robot routing, Proc. International Conference on Robotics: Science and Systems, 2005, 343–350.
  24. [24] M. Berhault, H. Huang, P. Keskinocak, S. Koenig, W. Elmaghraby, P. Griffin, and A. Kleywegt, Robot exploration with combinatorial auctions, Proc IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2003, 1957–1962.
  25. [25] S.S. Talay and T. Balch, A distributed multi-robot cooperation framework for real time task achievement, Distributed Autonomous Robotic Systems (DARS), 7, 2006, 187–196.
  26. [26] J. Melvin, P. Keskinocak, S. Koenig, C. Tovey, and B.Y. Ozkaya, Multi-robot routing with rewards and disjoint time windows, Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, San Diego, CA, 2007, 2332–2337.
  27. [27] J. Munkres, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics, 5 (1), 1957, 32–38.
  28. [28] L.A. Wolsey, Integer programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, 1998.
  29. [29] H.W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2, 1955, 83–97.
  30. [30] D. Jungnickel, Graphs, Networks, and Algorithms (Berlin: Springer-Verlag, 1999).
  31. [31] M.S. Bazaara, J.J. Jarvis, and H.D. Sherali, Linear programming and network flows (New York: John Wiley & Sons, 1990).
  32. [32] Y. Mei, Y.H. Lu, Y.C. Hu, and C.S.G. Lee, Deployment of mobile robots with energy and timing constraints, IEEE Transactions on Robotics, 22 (3), 2006, 507–522.
  33. [33] Official web site of the SICK LMS 200 laser rangefinder, https://www.mysick.com/eCat.aspx?go=FinderSearch&Cat=Gus&At=F&Cult=English&FamilyID=344&Category=Produktfinder&Selections=34243, 2010.
  34. [34] Official web site of the CANON CV-C4 PTZ camera, http://www.usa.canon.com/consumer/controller?act=ModelInfoAct&tabact=ModelTechSpecsTabAct&fcategoryid=262&modelid=7402, 2010.
  35. [35] Official web site of the gripper, http://www.activrobots.com/ACCESSORIES/gripper.html, 2010.

Important Links:

Go Back