Haksun Li
ABSTRACT
We study how agents can cooperate to revise their plans as they attempt to ensure that they do not over--utilize their local resource capacities. An agent in a multiagent environment should in principle be prepared for all environmental events as well as all events that could conceivably be caused by other agents' actions. The resource requirements to execute such omnipotent plans are usually overwhelming, however. Thus, an agent must decide which tasks to perform and which to ignore in the multiagent context. Our strategy is to have agents selectively communicate relevant details of their plans so that each gets a sufficiently accurate view of the events others might cause. Reducing uncertainties about the world trajectory improves the agents' resource allocation decisions and decreases their resource consumptions. In fact, our experiments over a sample domain show that, on average, 50% of an agent's initial actions are planned for states it can discover it will never reach. The protocol we develop in this paper thus discovers futile actions and reclaims resources that would otherwise be wasted.
- Atkins, E. M., Abdelzaher, T. F., Shin, K. G. and Durfee, E. H. Mar-Apr 2001. Planning and Resource Allocation for Hard Real-time, Fault-Tolerant Plan Execution. Journal of Autonomous Agents and Multi-Agent Systems. Google Scholar
Digital Library
- Boutilier. C. 1999. Sequential Optimality and Coordination in Multiagent Systems. IJCAI-99. Google ScholarDigital Library
- Conry, S. E., MacIntosh, D. J., and Meyer, R.A. 1990. DARES: A Distributed Automated Reasoning System. Proceedings of AAAI-90, pp. 78--85.Google Scholar
- Decker, K. and Lesser, V. 1995. Designing a Family of Coordination Algorithms. ICMAS-95.Google Scholar
- Durfee, E. H. and Lesser, V. R. September 1991. Partial Global Planning: A Coordination Framework for Distributed Hypothesis Formation. IEEE Transactions on Systems, Man, and Cybernetics, Special Issue on Distributed Sensor Networks, SMC-21(5):1167--1183.Google Scholar
- Ephrati, E., Pollack, M., and Rosenschein, J. S. 1995. A tractable heuristic that maximizes global utility through local plan combination. In Lesser, V., editor, Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95), pages 94--101, San Francisco, CA. MIT Press.Google Scholar
- Georgeff. M. 1983. Communication and Interaction in multi-agent planning. Proc. of the Third National Conference on Artificial Intelligence (AAAI-83), pp. 123--129.Google Scholar
- Kumar, S., Huber, M. J., Cohen, P. R., and McGee, D. R. 2002. Toward a Formalism for Conversation Protocols Using Joint Intention Theory. Computational Intelligence Journal (Special Issue on Agent Communication Language), Brahim Chaib-draa and Frank Dignum (Guest Editors), Vol. 18, No. 2, pages 174--228.Google Scholar
- Li, H, Atkins, E., Durfee, E. H. and Shin, K. G. August 2001. Practical State Probability Approximation for a Resource-Limited Real-Time Agent. Proceedings of the IJCAI-01 Workshop on Planning with Resources.Google Scholar
- Musliner, D. J., Durfee, E. H., and Shin, K. G. 1995. World Modeling for the Dynamic Construction of Real-Time Control Plans. Artificial Intelligence, vol. 74, pp. 83--127. Google ScholarDigital Library
- Shintani, T, Ito, T., and Sycara, K. 2000. Multiple Negotiations among Agents for a Distributed Meeting Scheduler. In Proceedings of the Fourth International Conference on Multi-Agent Systems (ICMAS'2000). Google ScholarDigital Library
- Shoham, Y. and Tennenholtz, M. February 1995. On Social Laws for Artificial Agent Societies: Off-Line Design. Artificial Intelligence, Vol. 73, Numbers 1-2, pp. 231--252. Google ScholarDigital Library
- Smith, R. G. December 1980. The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Transactions on Computers, C-29(12):1104--1113.Google Scholar
- Stankovic, J. A. October 1988. Misconceptions about Real-Time Computing: A Serious Problem for Next-Generation Systems. IEEE Computer, vol. 21, no. 10, pp.10--19. Google ScholarDigital Library
Index Terms
- Multiagent planning for agents with internal execution resource constraints
Recommendations
Recursive Reductions of Internal Dependencies in Multiagent Planning
ICAART 2016: Proceedings of the 8th International Conference on Agents and Artificial IntelligenceProblems of cooperative multiagent planning in deterministic environments can be efficiently solved both by distributed search or coordination of local plans. In the current coordination approaches, behavior of other agents is modeled as public external ...
Heuristic multiagent planning with self-interested agents
AAMAS '11: The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 3The focus of multiagent planning research has recently turned towards domains with self-interested agents leading to the definition of Coalition--Planning Games (CoPGs). In this paper, we investigate algorithms for solving a restricted class of "safe" ...
Multiagent Planning and Plan Execution
TAI '95: Proceedings of the Seventh International Conference on Tools with Artificial IntelligencePlanning by a multiagent system is done at two levels: first, the abstract group agent proposes a skeletal plan reasoning with the primary effects of the actions. Next, the individual agents execute the skeletal plan by reactively planning and executing ...
Comments