Loading...
Please wait, while we are loading the content...
Similar Documents
Reasoning about Coordination Costs in Resource-Bounded Multi-Agent Systems
| Content Provider | Semantic Scholar |
|---|---|
| Author | Raja, Anita |
| Copyright Year | 2004 |
| Abstract | Deliberative agents operating in open environments must make complex real-time control decisions on scheduling and coordination of domain activities. These decisions are made in the context of limited resources and uncertainty about the outcomes of activities. In this paper, we show that reasoning explicitly about the cost of control and domain actions leads to significant improvement in the performance of a multi-agent system. An empirical reinforcement learning algorithm which supports this reasoning process is presented. Open environments are dynamic and uncertain. Deliberative agents operating in these environments must reason about their local problem solving actions, coordinate with other agents to complete tasks requiring joint effort, plan a course of action and carry it out. These deliberations may involve computation and delays waiting for arrival of appropriate information. They have to be done in the face of limited resources, uncertainty about action outcomes and i n real-time. Furthermore, new tasks can be generated by existing or new agents at any time. These tasks have deadlines where completing the task after the deadline could lead to lower or no utility. This requires an agent to interleave deliberation with execution of its domain activities. The agent has to choose which deliberative actions to perform when and whether to deliberate or to execute domain actions that are the result of previous deliberative action s. To do this optimally, an agent would have to know the effect of all combinations of actions ahead of time, which is intractable for any reasonably sized problem. The ability to sequence domain and control actions without consuming too many resources in the process is called the meta-level control (MLC) for a resource-bounded rational agent. Our approach is to equip an agent with meta-level reasoning with bounded computational overhead. We consider three classes of deliberative actions: information gathering actions, coordination actions and planning/scheduling actions. These actions, also called contr ol actions, are non-trivial requiring exponential work in the number of domain actions. Copyright c © 2004, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. The first type of deliberative actions are information gathering actions which involve gathering information about th e environment which includes the state of other agents. This information is used to determine the relevant control actio ns. These actions do not use local processor time but they delay the deliberation process. The second type of deliberative action, coordination, is the process by which a group of agents achieve their tasks in a shared environment. In this work, coordination is the inte ragent negotiation process that establishes commitments on completion times of tasks or methods. Finally, the third type of deliberative actions involve planning and scheduli ng. Planning is the process in which the agent uses beliefs about actions and their consequences to search for solutions to on e or more high-level tasks(goals) over the space of possible plans. It determines which domain actions should be taken to achieve the tasks. Scheduling is the process of deciding when and where each of these actions should be performed. In this work, planning is folded into the scheduling process . The problem with most single and multi agent systems (Boutlier 1999; Musliner 1996; Raja, Lesser, & Wagner 2000; Kuwabara 1996; Zilberstein & Mouaddib 1999) is that they do not explicitly reason about the cost of deliberative computation. Hence, these systems have no way to trade-off the resources used for deliberative actions and d omain actions. An agent is not performing rationally if it fai ls to account for the overhead of computing a solution. This leads to actions that are without operational significance ( Simon 1976). We address this problem using a reinforcement learning-based approach. There has been a variety of work on meta-level control (Simon 1982; Harada & Russell 1999; Stefik 1981) but in reviewing the literature there is little that is directly re lated the meta-level control problem discussed in this paper. The difficult characteristics of our problem are the complexity of the information that characterize system state; the vari ety of responses with differing costs and parameters available to the situation; the high degree of uncertainty caused by the non-deterministic arrival of tasks and outcomes of prim itive domain actions; and finally the fact that the consequenc e of decisions are often not observable immediately and may have significant down-stream effects. The problem worked on that is closest to the complexity of our meta-level contro l decisions is the Guardian system(Hayes-Roth et al. 1994). However their system is knowledge intensive and the heuristic rules seem very domain-dependent in comparison to the domain-independence of our approach. Although (Hansen & Zilberstein 1996) and (Russell & Wefald 1992) are applicable to this work, the techniques used are limited to specifi c problem solving situations that were much more structured than those encountered in our domain. The intent of this research is to show that a meta-level reasoning component with bounded and small computation overhead can be constructed that significantly improves the performance of individual agents in a cooperative multiagent system. This paper is structured as follows: We first describe an example scenario which motivates the metalevel questions addressed in this work, including the need t o reason about control costs. This scenario exhibits partial observability, non-stationarity and action outcome uncerta inty which are characteristic of multi-robotic systems. A forma l description of the problem is then presented; followed by the empirical reinforcement algorithm which supports meta level control reasoning. Finally experimental results sho wing the effectiveness of meta-level control are provided us ing a hand-generated heuristic approach as well as the reinforcement learning approach. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://webpages.uncc.edu/anraja/PAPERS/AAAISS04.pdf |
| Alternate Webpage(s) | https://www.researchgate.net/profile/Victor_Lesser/publication/228846481_Reasoning_about_coordination_costs_in_resource-bounded_multi-agent_systems/links/02bfe51081d689bbad000000.pdf |
| Alternate Webpage(s) | http://mas.cs.umass.edu/Documents/Raja_AAAI-SS04.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
