Task allocation using a distributed market-based planning mechanism

ABSTRACT

This paper describes a market-based planning mechanism used for task and resource allocation within a larger distributed, multi-robot control and coordination architecture. We are developing an extension to the traditional three-layered robot architecture that enables robots to interact directly at each layer -- at the behavioral level, the robots create distributed control loops; at the executive level, they synchronize task execution; at the planning level, they use market-based techniques to allocate tasks and resources. This paper focusses on the market-based planning layer, which is comprised of two main components: a trader that participates in the market, auctioning and bidding on tasks; and a scheduler that determines task feasibility and cost for the trader, and interacts with the executive layer for task execution.

REFERENCES

• 1: Vincent A. Cicirello , Stephen F. Smith, Amplification of Search Performance through Randomization of Heuristics, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.124-138, September 09-13, 2002
• 2: M. B. Dias and A. Stentz. A free market architecture for distributed control of a multirobot system. In Proc. International Conference on Intelligent Autonomous Systems, pages 115--122, 2000.
• 3: M. B. Dias and A. Stentz. A market approach to multirobot coordination. Technical Report CMU-RI-TR-01-26, Robotics Institute, Carnegie Mellon University, 2001.
• 4: D. Goldberg, V. Cicirello, M. B. Dias, R. Simmons, S. Smith, and A. T. Stentz. Market-based multi-robot planning in a distributed layered architecture. In Proceedings from the 2003 International Workshop on Multi-Robot Systems. Kluwer Academic Publishers.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Autonomous vehicles

General Terms:
Algorithms, Experimentation

Keywords:
Mars exploration, distributed three-layered architecture, market economy, multi-robot control, stochastic scheduling