Probabilistic Analysis of Market-based Algorithms for Initial Robotic Formations
- 24 June 2009
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 29 (9) , 1154-1172
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- Market-based Multirobot Coordination for Complex TasksThe International Journal of Robotics Research, 2006
- Global and regional path planners for integrated planning and navigationJournal of Robotic Systems, 2005
- Sold!: auction methods for multirobot coordinationIEEE Transactions on Robotics and Automation, 2002
- The ζ(2) limit in the random assignment problemRandom Structures & Algorithms, 2001
- DAMN: a distributed architecture for mobile navigationJournal of Experimental & Theoretical Artificial Intelligence, 1997
- Parallel synchronous and asynchronous implementations of the auction algorithmParallel Computing, 1991
- On the solution of the random link matching problemsJournal de Physique, 1987
- On the Expected Value of a Random Assignment ProblemSIAM Journal on Computing, 1979
- On Approximation Methods for the Assignment ProblemJournal of the ACM, 1962
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955