In this paper, we present a probabilistic analysis approach for analyzing market-based algorithms applied to the initial formation problem. These algorithms determine an assignment scheme for associating individual robots with goal positions necessary to achieve a desired formation while minimizing an objective function. The main contribution of this paper is a method that calculates the expected value of the objective function, which allows us to estimate and compare theoretically the performance of two task allocation algorithms. This probabilistic analysis is applied in different runtime scenarios. We validate our approach through both simulations and experiments with real robots.
Aldous, D.J. ( 2001). The ζ (2) limit in the random assignment problem . Random Structures Algorithms, 18(4): 381-418.
2.
Bertsekas, D.P. ( 1981). A new algorithm for the assignment problem. Mathematical Programming, 21(1): 152-171.
3.
Bertsekas, D.P. and Castañon, D.A. ( 1991). Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Computing, 17(6-7): 707-732.
4.
Botelho, S.C. and Alami, R. ( 1999). M+: a scheme for multirobot cooperation through negotiated task allocation and achievement. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Detroit, MI.
5.
Calafiore, G., Dabbene, F. and Tempo, R. ( 1998). Uniform sample generation in l p balls for probabilistic robustness analysis. Proceedings IEEE Conference on Decision and Control, Tampa, FL, pp. 3335-3340.
6.
Coppersmith, D. and Sorkin, G.B. ( 1999). Constructive bounds and exact expectations for the random assignment problem. Random Structures and Algorithms, 15(2): 133- 144.
7.
Dias, M., Zinck, M.B., Zlot, R.M. and Stentz, A. ( 2004). Robust multirobot coordination in dynamic environments . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), New Orleans, LA, pp. 3435-3442.
8.
Dias, M., Zlot, R., Karla, N. and Stentz, A. ( 2006). Market-based multirobot coordination: a survey and analysis . Proceedings of the IEEE, 94(7): 1257-1270.
9.
Gerkey, B. and Mataric, M.J. ( 2000). Murdoch: publish/subscribe task allocation for heterogeneous agents. Proceedings of the 4th International Conference on Autonomous Agents, Barcelona, Spain, pp. 203-204.
10.
Gerkey, B. and Mataric, M. J. (2002). Sold!: auction methods for multi-robot coordination. IEEE Transactions on Robotics and Automation , 18(5): 758-768.
11.
Howard, A., Seraji, H. and Werger, B. ( 2005). Global and regional path planners for integrated planning and navigation. Journal of Robotic Systems, 22(12): 767-778.
12.
Howard, A. and Viguria, A. ( 2007). Controlled reconfiguration of robotic mobile sensor networks using distributed allocation formalisms. NASA Science Technology Conference (NSTC), College Park, MD.
13.
Koenig, S., Tovey, C., Zheng, X. and Sungur, I. ( 2007). Sequential bundle-bid single-sale auction algorithms for decentralized control. Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1359-1365.
14.
Kuhn, H. ( 1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2: 83- 97.
15.
Kurtzberg, J.M. ( 1962). On approximation methods for the assigment problem. Journal of the ACM, 9(4): 419-439.
16.
Lagoudakis, M., Berhault, M., Koenig, S., Keskinocak, P. and Kleywegt, A. ( 2004). Simple auctions with performance guarantees for multi-robot task allocation. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), vol. 1, Sendai, Japan, pp. 698- 705.
17.
Lagoudakis, M., Markakis, V., Kempe, D., Keskinocak, P., Koenig, S., Kleywegt, A., Tovey, C., Meyerson, A. and Jain, S. ( 2005). Auction-based multi-robot routing. Proceedings of Robotics: Science and Systems, Cambridge, MA.
18.
Lawler, E.L. ( 1985). The Traveling Salesman Problem. New York, John Wiley and Sons.
19.
Maza, I., Viguria, A. and Ollero, A. ( 2006). Networked aerial-ground robot system with distributed task allocation for disaster management. Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics, Gaithersburg, MD.
20.
Mézard, M. and Parisi, G. ( 1987). On the solution of the random link matching problems . Journal de Physique, 48(9): 1451-1459.
21.
Ollero, A. and Amidi, O. ( 1991). Predictive path tracking of mobile robots. Proceedings of 5th International Conference on Advanced Robotics, Robots in Unstructured Environments (ICAR), Vol. 2, pp. 1081-1086.
22.
Rosenblatt, J.K. ( 1997). DAMN: a distributed architecture for mobile navigation . Journal of Experimentation and Theoretical Artificial Intelligence , 9(2): 339-360.
23.
Smith, G. ( 1980). The contract net protocol: high-level communication and control in a distributed problem solver. IEEE Transactions on Computers, 29(12): 1104-1113.
24.
Smith, S.L. and Bullo, F. ( 2007). Target assignment for robotic networks: asymptotic performance under limited communication. Proceedings of the American Control Conference, New York, pp. 3585-3590.
25.
Thrun, S., Burgard, W. and Fox, D. ( 2005). Probabilistic Robotics (Intelligent Robotics and Autonomous Agents). Cambridge, MA, The MIT Press.
26.
Viguria, A. and Howard, A. ( 2007). Upper-bound cost analysis of a market-based algorithm applied to the initial formation problem. Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), San Diego, CA, pp. 2326-2331.
27.
Viguria, A. and Howard, A. ( 2008). Videos of the experiments. http://grvc.us.es/∼antidio/ijrr_2008.html.
28.
Viguria, A. and Howard, A. ( 2009). An integrated approach for achieving multi-robot task formations. IEEE/ASME Transactions on Mechatronics, 14(2): 176-186.
29.
Viguria, A., Maza, I. and Ollero, A. ( 2007). SET: an algorithm for distributed multirobot task allocation with dynamic negotiation based on task subsets. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy, pp. 3339-3344.
30.
Walkup, D.W. ( 1979). On the expected value of a random assignment problem . SIAM Journal on Computing, 8: 440- 442.
31.
Yun, S. and Rus, D. ( 2007). Optimal distributed planning of multi-robot placement on a 3D truss. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), San Diego, CA, 1365-1370.
32.
Zavlanos, M.M. and Pappas, G.J. ( 2007). Dynamic assignment in distributed motion planning with limited information. Proceedings of the American Control Conference, New York, pp. 1173-1178.
33.
Zlot, R. and Stentz, A. ( 2006). Market-based multirobot coordination for complex tasks . The International Journal of Robotics Research, 25(1): 73-101.
