Task selection problem under uncertainty as decision-making

ABSTRACT

In this paper, we address the problem of decision-making under uncertainty for the task selection problem. We consider an environment where an agent has to select tasks to execute in a way which maximizes his gain. The main motivation is the new challenging applications such as planetary rovers, e-commerce, combinatorial auction and vehicle routing where agents are with limited resources and have to distribute and execute a set of tasks under uncertainty. In the model proposed in this paper, we formulate the local task selection as a \textitMarkov Decision Process (MDP). In fact, the MDP allows agents to deal with two sources of uncertainty : (1) the uncertainty on the task allocation, and (2) the uncertainty on the consumption of resources required for executing each task. We will also show how an agent can improve his knowledge about the environment.

REFERENCES

• 1: M.R. Andersson and T.W Sandholm. Contract types for satisficing task allocation: 2 experimental results. In Proceedings of AAAI 1998 Spring Symposium: Satisficing Models, pages 1--7, Stanford University, CA, Mar 1998.
• 2: Martin Andersson , Tuomas Sandholm, Time-quality tradeoffs in reallocative negotiation with combinatorial contract types, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.3-10, July 18-22, 1999, Orlando, Florida, United States
• 3: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 4: R. E. Bellman. A markov decision process. journal of Mathematical Mechanics, pages 6:679--684, 1957b.
• 5: Craig Boutilier , Moisés Goldszmidt , Bikash Sabata, Sequential Auctions for the Allocation of Resources with Complementarities, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.527-523, July 31-August 06, 1999
• 6: Maroua Bouzid , Hossam Hanna , Abdel-Illah Mouaddib, Deliberation Levels in Theoretic-Decision Approaches for Task Allocation in Resource-Bounded Agents, Balancing Reactivity and Social Deliberation in Multi-Agent Systems, From RoboCup to Real-World Applications (selected papers from the ECAI 2000 Workshop and additional contributions), p.198-216, January 2001
• 7: Tara Estlin , Alexander Gray , Tobias Mann , Gregg Rabideau , Rebecca Castaño , Steve Chien , Eric Mjolsness, An integrated system for multi-rover scientific exploration, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.613-620, July 18-22, 1999, Orlando, Florida, United States
• 8: White D. J. Markov Decision Processes. West Sussesx, England : John Wiley & Sons, 1993.
• 9: M. L. Puterman. Markov decision processes. Wiley, 1994.
• 10: Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
• 11: Tuomas Sandholm, eMediator: a next generation electronic commerce server, Proceedings of the fourth international conference on Autonomous agents, p.341-348, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337522]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

General Terms:
Theory

Keywords:
Markov decision process, decision under uncertainty, distributed agents, intelligent agents, resource-bounded agents