AGENT-BASED COLLABORATIVE PLAN ADAPTATION WITH RESOURCE CONSTRAINTS

ABSTRACT

One important lesson learned from the crisis of Hurricane Katrina is that preplanned allocation of scarce resources (e.g., helicopters, vehicles, medical equipment, etc.) must be dynamically modified to adapt to the changing situation. Furthermore, multiple response teams, which own different resources, need to collaborate to determine tradeoffs among competing resource needs to reallocate such resources. The challenge of this collaborative resource reallocation is further complicated by the fact that each team may not have complete information about other teams’ resources and the utility of their tasks. This limitation makes it difficult to assess tradeoffs among resource needs of different teams.

In order to solve such problems, this research developed team-based software intelligent agents to collaboratively adapt existing plans for resource use by consistently reallocating the limited resources among distributed tasks. Based on an innovative multiagent teamwork model called R-CAST (RPD-enabled Collaborative Agents for Simulating Teamwork), this research developed a framework for collaborative plan adaptation under resource constraints. The framework addresses the challenges mentioned above in three ways. First, it extends R-CAST with explicit representation of resources and related reasoning algorithms about resources. Second, it uses a combinatorial auction mechanism to enable agents to exchange utility information regarding competing needs of bundled resources, so that agents can reason about resource tradeoffs for effective reallocation of scarce resources. Third, the framework implements an algorithm for an agent to assess the opportunity cost of offering a resource bundle that has already been assigned to a task. The algorithm considers alternative ways to accomplish the task, the utility of such alternatives, and associated costs for obtaining required resources.

In summary, the work presented in this thesis facilitates distributed teams to reason about tradeoffs among competing requests for resource bundles by exchanging relevant information through combinatorial auctions. Experimental results have suggested that this research can significantly improve the utilization of limited resources in adapting plans to the dynamic situation.

 

TABLE OF CONTENTS

LIST OF FIGURES ………………………………………………………………………………………..ix

LIST OF TABLES………………………………………………………………………………………….xi

ACKNOWLEDGEMENTS……………………………………………………………………………..xii

Chapter 1  Introduction……………………………………………………………………………………1

1.1 Problem Statement………………………………………………………………………………1

1.2 Motivation………………………………………………………………………………………….3

1.3 Research Scope…………………………………………………………………………………..11

1.4Research Questions…………………………………………………………………………….14

1.5 The Accomplishment of This Research………………………………………………….15

1.6 Thesis Organization…………………………………………………………………………….18

Chapter 2  Related Work………………………………………………………………………………….19

2.1 Overview……………………………………………………………………………………………19

2.2 Planning and Plan Representation …………………………………………………………21

2.3 Resource Constraint Reasoning and Scheduling……………………………………..24

2.4 Plan Adaptation ………………………………………………………………………………….28

2.5 Distributed Planning……………………………………………………………………………31

2.5.1Abstraction Plan Decomposition…………………………………………………32

2.5.2Plan Merging ……………………………………………………………………………33

2.6 Agent-based Teamwork……………………………………………………………………….36

2.6.1 Teamwork Theory……………………………………………………………………..37

2.6.2 Agent-based Teamwork Architecture……………………………………………38

2.7 Market-based Agents…………………………………………………………………………..41

2.8 Summary……………………………………………………………………………………………44

Chapter 3  A Framework for Collaborative Plan Adaptation (CPA) with Resource

Constraints………………………………………………………………………………………………45

3.1Overview…………………………………………………………………………………………..45

3.2R-CAST based Agent Architecture ………………………………………………………50

3.3 Resource Constraint…………………………………………………………………………….54

3.3.1Resource Representation ……………………………………………………………55

3.3.1.1Resource Status ……………………………………………………………….55

3.3.1.2Resource Requirement ……………………………………………………..58

3.3.2Resource Needs Reasoning ………………………………………………………..61

3.4Adaptive Resource Allocation……………………………………………………………..62

3.4.1Market Mechanism……………………………………………………………………63

3.4.2Combinatorial Auctions for Bundled Resources……………………………65

3.4.3Auction-based Resource Reallocation………………………………………….69

3.4.3.1Bid Price…………………………………………………………………………73

3.4.3.2Algorithms………………………………………………………………………76

3.4.3.3Utility Update………………………………………………………………….83

3.5Utility-based Task Method Selection ……………………………………………………83

3.5.1Notations………………………………………………………………………………….87

3.5.2Opportunity Cost ………………………………………………………………………88

3.5.3Further Discussion on Alternative Methods………………………………….90

3.6 Discussions………………………………………………………………………………………..94

3.6.1 Scope of the CPA Framework……………………………………………………..94

3.6.2 Comparison with Peer Work ……………………………………………………….96

3.6.3Implementation Guideline………………………………………………………….98

3.7 Summary……………………………………………………………………………………………101

Chapter 4  Experiments and Results………………………………………………………………….103

4.1Introduction……………………………………………………………………………………….104

4.2. Scenario Design and Experiment Settings……………………………………………105

4.2.1A Hurricane Relief Scenario ………………………………………………………106

4.2.2Configurations of Three Teams…………………………………………………..111

4.3Procedure………………………………………………………………………………………….115

4.4Data Analysis and Results…………………………………………………………………..118

4.5 Summary…………………………………………………………………………………………..125

Chapter 5  Conclusions and Future Work…………………………………………………………..127

5.1Contributions …………………………………………………………………………………….128

5.2Future Work………………………………………………………………………………………130

Bibliography ………………………………………………………………………………………………….132

Appendix A  Agent Configuration Example ………………………………………………………144

Appendix B  Predefined Plans………………………………………………………………………….148

 

LIST OF FIGURES

Figure 1.1: The Overview of Collaborative Plan Adaptation under a Dynamic

Environment ……………………………………………………………………………………………10

Figure 2.1: An Example of STRIPS Operator Representation[14] …………………………22

Figure 2.2: The Flow of Distributed Planning…………………………………………………….32

Figure 2.3: An Overview of CAST Architecture………………………………………………40

Figure 3.1: The Resource-constrained Collaborative Plan Adaptation Framework…49

Figure 3.2: R-CAST Architecture[83] ……………………………………………………………….50

Figure 3.3: The CPA Agent Architecture Extended from R-CAST………………………52

Figure 3.4: A Example of Combinatorial Auction……………………………………………….66

Figure 3.5:The Auction Process for Adaptive Resource Allocation……………………..70

Figure 3.6: An Example of Indirect Resource Needs…………………………………………..91

Figure 3.7: The LivingLab Approach for Problem Solving (McNeese et al. 2005)….99

Figure 4.1: A Hurricane Relief Scenario ………………………………………………………….108

Figure 4.2: Resource Coordinator Interface………………………………………………………116

Figure 4.3: Performance by Global Utility for Each Team …………………………………..119

Figure 4.4: Performance by Number of Completed Task Instances……………………….120

Figure 4.5: The Residual Plot for Experimental Data………………………………………..124

 

LIST OF TABLES

Table 2-1: Overview of Related Work……………………………………………………………….20

Table 3-1: Two Structures for Resource Representation……………………………………..57

Table 3-2: An Example Plan for Delivering Stuffs to a Destination……………………..60

Table 3-3: The Acceptable Bid-Sets  for the Combinatorial Auction Example………67

Table 3-4: A Plan with Alternative Methods to Accomplish a Task……………………..86

Table 3-5: Comparisons of the proposed CPA Framework and Related Work……….97

Table 4-1: A Plan Example……………………………………………………………………………..110

Table 4-2: Resource Types ……………………………………………………………………………..111

Table 4-3: Resource Information of Three Basic Task Instances………………………….113

Table 4-4: Initial Resource Distribution ……………………………………………………………114

Table 4-5: Comparing The Global Utility …………………………………………………………119

Table 4-6: Paired T-test Results for Team A and Team B …………………………………..122

Table 4-7: Paired T-test Results for Team B and Team C……………………………………123

 

Chapter 1

 

Introduction

1.1 Problem Statement

The crisis of meeting the emergency needs caused by Hurricane Katrina reveals the importance of consistently adapting preplanned tasks and handling emergencies with scarce resources under a dynamic, real-time situation. Due to the naturally evolving characteristics of such a situation, existing plans for completing rescue tasks are subject to unexpected changes during the execution process. Thus, those plans must be modified in an appropriate and timely way to keep them from failing. Also, certain changes during the response to such an occurrence as Katrina trigger additional tasks, which may generate new requests for resources.

Since the available resources are always limited in such emergency situations, tradeoffs have to be made judiciously in order to switch resources from a previously existing task to a new task and thus get a higher total resource utility.

Similar to the hurricane relief domain, many other real-world domains (e.g., emergency first response, military actions, and anti-terrorism, etc.) also require plan adaptation, especially the adaptation of resource allocation, in order to handle changes in a timely and effective way. Such adaptation is necessary because conflicts often arise among different tasks regarding their resource needs since the number of resources needed may exceed the number available. How to satisfactorily resolve conflicts when different tasks compete for the same resources becomes the key problem that needs to be addressed. This problem is further complicated when scarce resources are owned by distributed teams, each of which needs to allocate resources among the tasks assigned to them, because each team has only limited information about the other teams’ resources and situations.

There are two common characteristics in such domains that have prompted this research on plan adaptation. First, the situation is always changing, which makes it possible that either emerging tasks are triggering additional resource requests or some previously available resources have become unavailable. Second, there are only limited resources, which make it infeasible to satisfy every task’s resource requirement and complete all those tasks. People usually have to make tradeoffs when selecting tasks so as to satisfy the resource requirement. In other words, those tasks should be selected in a way that optimizes the expected utility of the limited resources.

When multi-agent systems (MAS) applications are deployed in such uncertain, dynamic environments, those issues also need to be carefully considered. Although centralized mechanisms to solve the optimization problem can provide qualityguaranteed solutions, they are often not scalable and can create a “bottleneck” problem. Distributed solutions can be more flexible and more reliable, although these benefits are obtained through extra efforts in coordinating multiple agents. Due to the fact that each agent has only partial knowledge about others’ resources and states, the coordination problem becomes more complicated. This thesis therefore focuses on designing and implementing a market-based mechanism to dynamically optimize the reallocation of limited resources among distributed teams by making tradeoffs among competing resource needs based on exchanging utility-based price information.

1.2 Motivation

Problems with planning have had a long history in the field of Artificial Intelligence (AI). Traditional approaches to AI planning problems usually assume that the context is static and predictable in order to simplify the planning process [1] . Unfortunately, the real world is changing and unpredictable to a certain degree. If the planner neglects uncertainties in the real world, it will not be able to anticipate potential risks and to make preparation for handling those problems. As a result, the planning system will run into a dilemma when unexpected changes occur and fail to solve emerging problems to achieve the desired goal. Thus, recently there has been an increasing need for developing adaptive planning systems that work in a complex, dynamically changing environment, especially in crises of the proportion of Hurricane Katrina. The planning problem is no longer a one-time issue since static plans are not the ultimate goal of successful planning systems, and planners need to adapt current plans to the change online. Simply speaking, plan adaptation means modifying or repairing an old plan so it can solve a new problem by reusing part of the old plan. The approach of adapting previously successful plans is an attractive paradigm for the following two reasons. First, cognitive studies show that human experts depend on knowledge of past problems and solutions––which can be called experience––for good problem-solving performance. Second, arguments about computational complexity show that reasoning from first principles requires time exponential to the size of the problem. Systems that reuse old solutions can potentially avoid this problem by solving a smaller problem: that of adapting a previous solution to the current task. Actually, because many new problemsolving situations closely resemble previous situations, there may be an advantage to using the principles of past successes to solve new problems [2] .

Agent-based systems technology has been developed in AI as a new paradigm for conceptualizing, designing, and implementing software systems. There are numerous definitions for “intelligent agents” in AI communities. Here we adopt the definition provided by the Intelligence Software Agents Lab at Carnegie Mellon University to generally describe what an agent and a multi-agent system are in this research. Based on this definition, agents are sophisticated computer programs that act autonomously on behalf of their users, across open and distributed environments, to solve a growing number of complex problems. Increasingly, however, applications require multiple agents that can work together. A multi-agent system (MAS) is a loosely coupled network of software agents that interact to solve problems that are beyond the individual capacities or knowledge of each problem solver [3] .

Many researchers have addressed the plan adaptation problem for a single agent

[4, 5, 2] . However, large-scale adaptive planning problems in many real-world domains (e.g., hurricane relief, homeland security, military, etc.) usually require multiple agents including human planners to collaborate on a solution. For example, in the military domain, a mission plan may involve hundreds or thousands of units being deployed simultaneously. Since the real-world situation changes frequently, a huge amount of information regarding the changes needs to be communicated among those units and each must process the exchanged information about the changes in a timely manner to adapt its own subplan correctly, and to communicate the result in order not to corrupt others’ tasks. If this process is performed by humans, it is usually time consuming to produce the result and incurs huge cognitive loads. The key issue is that it distracts the human units from focusing on the big picture and divides their attention between the high-level tasks (at which humans are proficient) and the low-level information exchange and analysis (which are intelligent agents’ advantages). Ideally, when an existing plan has to be adapted for responding to the changes, the expertise of different agents (both software agents and human planners) needs to be synthesized to enhance the overall performance. Usually, intelligent agents can gather and preprocess information needed in the plan adaptation process more quickly and accurately. Human experts may have a complete overview of the whole scenario from the information provided by intelligent agents and are able to generate better solutions based on their experiences and advanced reasoning abilities. Using such a collaborative method to solve the plan adaptation problem can speed up the process, reduce human labor, improve efficiency, and make it possible to handle information-overloaded tasks. Obviously, how intelligent agents can cooperate together effectively in this process is a challenging issue to address.

Resource is another important issue motivating this research. Usually a plan has its specific resource requirement in addition to preconditions. Only when both the resource requirement and preconditions are satisfied can the plan be executed successfully. However, under a situation in which the total available resources are limited, it may be not possible to satisfy the resource requirement for all tasks at the same time.

The scarce resources should then be allocated to selected tasks in a way that maximizes the expected utility. Also, the allocation of resources should not be fixed but dynamic in order to handle the case when there are emerging tasks or changes in the resource status of existing tasks. Consistently reallocating resources among distributed tasks is considered a significant part of the plan adaptation process, and is the focus of this research as well.

The scarcity of resources necessitates tradeoffs, and tradeoffs result in an opportunity cost. While the cost of a good or service often is thought of in monetary terms, the opportunity cost of a decision is based on what must be given up (the next best alternative) as a result of the decision. Any decision that involves a choice between two or more options has an opportunity cost. This research addresses the issue of opportunity cost when an agent is making a decision on whether to offer resources assigned to its own task by considering tradeoffs among alternative ways to accomplish the task.

From the encyclopedia of economics edited by David Henderson [87] , in economics the term “opportunity cost” of a resource means the value of the next-highestvalued alternative use of that resource. If, for example, you spend time and money going to a movie, you cannot spend that time at home reading a book, and you cannot spend the money on something else. If your next-best alternative to seeing the movie is reading the book, then the opportunity cost of seeing the movie is the money spent plus the pleasure you forgo by not reading the book. The wordopportunity in opportunity cost is actually redundant. The cost of using something is already the value of the highest-valued alternative use. But as contract lawyers and airplane pilots know, redundancy can be a virtue. In this case, its virtue is to remind us that the cost of using a resource arises from the value of what it could be used for instead.

In recent years, developing effective multi-agent systems to solve complex problems in dynamic, real-world domains has drawn more and more AI researchers’ attention. My research followed this tendency and was motivated to enable multiple software agents to collaboratively adapt existing plans by evaluating changes, sharing utility information, and optimizing the resource allocation. As a result, the allocation of limited resources is not just done at the beginning stage and not changed throughout the plan execution. Instead, resources are consistently being reallocated among tasks to adapt to changes arising from either the environment or the tasks themselves. The objective of dynamic resource reallocation is not only to satisfy some tasks’ resource requirement but also to optimize the resource allocation and maximize the expected utility from a global perspective.

The following paragraphs give a high-level description of how multiple agents collaborate with each other to adapt existing plans online regarding the resource constraint. Whenever an agent detects a change, first it analyzes the impact of the change and decides whether to let its teammates know this information. Then, if the change is relevant, the agents exchange information about the impact of this change on each individual plan (from the local view). Based on more complete information of how the change affects the total plans (from the global view), finally the agents collaboratively generate a response to the change, trying to optimize the global performance.

Section 1.1 briefly describes the problem of adapting preplanned tasks with limited resources to changes in various dynamic, real-time domains. Here an overview of the collaborative plan adaptation in a hurricane relief scenario is presented to further illustrate the problem and how multiple agents can collaborate to solve it (Figure 1.1).

Three kinds of tasks are involved: 1) delivering foods to a large group people who have been isolated in a flooded area (DeliverFood_Plan); 2) transferring sand bags and other materials to a specific place in order to fix a broken levee (FixLevee_Plan); and 3) rescuing a few persons from a dangerous place that will soon be flooded (RescuePeople_Plan). Each task has a predefined plan template, which specifies the plan’s goal, resource requirement, preconditions, and the process structure, etc. It is possible that multiple plan instances may be triggered from the same plan template by binding plan variables with different values. For example, the plan template RescuePeople_Plan has two instances. Each plan instance can be executed by a single agent or by a team of agents. In addition to agents who are executing those plan instances, each plan has a coordinator agent, who is responsible for gathering information about detected changes, analyzing the impact of changes, collaborating with other coordinators, and adapting the assigned plan instance. Since my research focuses on changes that impact a plan’s resource requirement, the coordinator agent can be called a resource coordinator. And the collaboration studied here is the one between multiple resource coordinators rather than between agents who are executing a plan in a teamwork context^[1] .

A resource coordinator generates requests for missing resources in its designated plan, handles resource requests from other coordinators, evaluates tradeoffs between keeping requested resources being allocated to its own plan and transferring them to the requesters, and makes the allocation decision based on the principle of maximizing the total expected utility of all plan instances.

There are many interactions between resource coordinators involved in the whole process. Communication is certainly a key issue since different coordinators need to share relevant information such as detected changes, the impact of changes, resource availability, and utility, etc. When conflicts arise due to multiple tasks competing for limited resources at the same time, coordinators have to interact with each other to make tradeoffs in selecting which resource requests to satisfy. For example, if both a RescuePeople_Plan instance P1 and a DeliverFood_Plan instance P2 are competing for a helicopter as the needed resource, their resource coordinators should work together to make a tradeoff to solve the conflict. In this specific case, the tradeoff is made to allocate the helicopter to P1 instead of P2 since the expected utility of rescuing people is much greater than the expected utility of delivering foods so that the total utility is maximized. Usually after the decision of allocating resources is made, coordinators who currently own the requested resources start a process to transfer them to where the requesting agent or team can access those resources.

1.3 Research Scope

The scope of collaborative plan adaptation is vast. It involves both traditional AI planning techniques (e.g., adaptive planning, knowledge representation, and plan execution, etc.) and multi-agent system features (e.g., team structure, shared mental model, and coordination, etc.). My research focuses on creating distributed intelligent computational systems that adapt existing plans online to solve potential resource conflicts caused by the changes in the situation, whereas re-planning from first principles is not part of this research. Existing plans are formed offline by either human experts or planning systems. Advanced techniques such as an agent-based teamwork model, marketbased mechanism, and optimization algorithms are integrated into the proposed framework to solve the plan adaptation problem with resource constraints in a distributed manner. As mentioned before, coordination is a key issue to be addressed in the adaptation process. My research adopts the approach to solve the issue of multi-agent coordination by leveraging on a multi-agent architecture from the teamwork perspective.

In order to make an agent-based collaborative plan adaptation applicable in real complex situations, the following steps need to be covered. First, theories of collaboration or teamwork should be extended to include the plan manipulation. Different from many other collaborative works, which focused on behaviors or actions, the process of collaborative plan adaptation is much related to coordination among multiple cognitive processes, which are highly interdependent. In the human case, it is mainly a collection of mental activities from different people (often domain experts). And the result of the adaptive planning process will decide the following collaborative behaviors and actions. The plan adaptation also involves the issue of making the best decision under the current and projected circumstances. Thus, existing theories need to consider this aspect and new features or new theories may need to be developed to consolidate the theoretical background. Second, due to the complexity of the large-scale plan adaptation problem under the dynamic world, intelligent agents need to interact with the human to make a better decision among a list of candidate options, or to get more specific information that is out of their local knowledge base. Thus, the role of the human should be included in the teamwork model in order to enhance the overall performance for solving a complex, realistic task. In other words, a user-friendly interface should be provided for human experts to interact with agents in a convenient and effective way in solving the adaptation problem. Third, after initial theories, models or designs, so called prototypes, are developed, we need to verify and modify them in an iterative procedure. Directly implementing them into the real world is risky, costly, and uncontrollable. Thus, we should test our ideas in a scaled world that simulates the real environment. Basically, we need to develop simulators in which we can easily test certain variables while constraining other irrelevant ones at much lower costs. In my research, the last two steps are included but the first step is not in the scope.

Below I list five assumptions under which this research is carried out. The proposed framework, algorithms and experimental results are valid if and only if those assumptions hold.

1. The total resources are limited, which means there are always more resource needs than available resources; otherwise there will not be conflicts in competing resources.
2. One task may have multiple methods to accomplish its goal while different methods have different utilities and different resource requirements.
3. Different tasks have reserved their own resources at the beginning stage and the knowledge about such private resources is not shared with other tasks.
4. Utility information for resources and tasks is distributed among different resource coordinators initially.
5. There are always communication costs when a coordinator needs to share certain information with other teammates.

1.4 Research Questions

The discussion above indicates the key issue in collaborative plan adaptation, which is how a team of agents can collaborate effectively in handling the changes. Interaction between agents occurs because agents solve subproblems that are interdependent, either through competing for resources or through relationships among the subproblems. Due to the complexity of solving problems in real-world domains, it is usually not possible to generate a perfect decomposition so that the computational requirements for effectively solving each subproblem and the location of information, expertise, processing, and communication resources in the agent network are totally independent [6] . This lack of a perfect fit often leads to a situation where there may be insufficient local information or resources for an agent to completely or accurately solve its assigned subproblems through its own processing. Plan adaptation in real-time requires each agent to handle the changes timely and correctly. Otherwise, even after a global plan has been developed, it may become inapplicable under the changed situation. Information sharing is the most useful way for multiple agents to coordinate their processes. However, communicating every piece of information is not an efficient solution because it involves extra costs when the information is not necessary. Resource constraint is another issue that cannot be neglected in the coordination process. Since the total resources are limited, conflicts usually arise due to different agents competing for the same resource at the same time when they are adapting their own plans to the changes. Moreover, these conflicts should not be solved simply by choosing the winner randomly or based on rules (e.g., first in first serve, priority, etc). Instead resource conflicts should be resolved in a way whereby the global utility is maximized (i.e., the limited resources can be fully utilized).

The research presented in this thesis focuses on two research questions: 1) how an agent can efficiently share information about the change and its impact on other teammates in a timely way and 2) how a team of agents can effectively collaborate on an optimal solution for resolving resource conflicts in adapting existing plans.

1.5 The Accomplishment of This Research

In this research, I studied the problem of adapting distributed plans to changes online and provided a solution based on dynamic resource allocation to solve conflicts between competing needs for scarce resources in an efficient way. First, a theoretical framework for a collaborative plan adaptation with resource constraints was proposed in this research. This framework consists of different functional components, which are integrated to facilitate the whole process of adapting plans to resource-related changes. With the guidance of such a framework, I built the resource coordinator agents on top of a novel multi-agent architecture called R-CAST (RPD-enabled Collaborative Agents for Simulating Teamwork). In addition to existing modules (e.g., task manager, active knowledgebase, information manager, etc.) in R-CAST, I extended it by implementing a resource manager module, which is used to monitor resource status, generate resource requests, and handle incoming resource requests. Last, I developed a market-based mechanism for dynamically optimizing the allocation of limited resources, and implemented an algorithm for a resource coordinator to select the right one from alternative methods in a task based on utility information and other tasks’ resource needs.

In summary, this research makes four major contributions to the field of plan adaptation.

1. Proposed a theoretical framework for collaborative plan adaptation with resource constraint. Different functional components are integrated within this framework to support the adaptation process in a distributed way. With this framework, resource coordinators can share relevant information (such as utility, resource status, resource requirement, etc.), and collaborate with each other to reach a global agreement on how to allocate resources to achieve the maximum utility. The framework enables a team of agents to collaboratively resolve conflicts among competing resource needs to adapt plans to the changing environment, based on assessing tradeoffs among those competing resource needs: 1) It uses a combinatorial auction for the team of agents to exchange information about opportunity cost. 2) An agent assesses its opportunity cost for offering a resource assigned to a task T_i by considering the tradeoff between alternative ways to accomplish T_i .
2. Built resource coordinator agents on top of a novel multi-agent architecture R-CAST with extended functions. Each resource coordinator is responsible for managing resources for its assigned task^[2] , and interacting with other resource coordinators in the adaptation process. R-CAST is extended with explicit representation of resources and related reasoning algorithms to generate resource needs and requests.

3. Developed an agent-based auction mechanism to enable resource coordinators to exchange utility information on their own tasks regarding competing resource needs. Thus, the allocation of limited resources is optimized and gives out the maximum global utility.
4. Designed and implemented an algorithm for a resource coordinator to evaluate alternative methods in a task and select the appropriate one based on utility information and resource needs of other coordinators. Usually, there are multiple methods to complete the same task, and different methods have different resource requirements. The algorithm enables a resource coordinator to assess tradeoffs between those alternative methods considering the impacts of selecting a method on both its own assigned task and other tasks.

Experimental results show that with the collaboration of resource coordinators, limited resources can be dynamically allocated to distributed tasks in adapting to resource-related changes. The market-based optimization mechanism makes it possible to fully utilize those limited resources and achieves a maximized global utility. And the method selection algorithm provides the flexibility and the optimality for completing a task from a broad view.

1.6 Thesis Organization

The remainder of the thesis is organized as follows. Chapter 2 introduces the background knowledge of distributed planning, plan adaptation, resource constraint reasoning, agent-based teamwork, and market-based optimization, and reviews related works. Chapter 3 presents a framework for collaborative plan adaptation (CPA) under resource constraints and explains how it leverages on a novel multiagent architecture RCAST. We elaborate the market-based approach to optimize resource reallocation during the adaptation process in Chapter 4. Chapter 5 explains how to select the appropriate method to complete a task if there are multiple options in order to maximize the expected utility based on more complete information. Experimental results are shown and analyzed in Chapter 6. Finally, Chapter 7 concludes the thesis.

[1] In the rest of this thesis, if not designated otherwise, an agent means an agent assuming the role of resource coordinator.

[2] A resource coordinator’s assigned task is not the task that the coordinator needs to execute, which is the ordinary meaning of “assigned task.” In this thesis, it actually means that the task is being managed by a resource coordinator.  The resource coordinator is responsible for satisfying the task’s resource needs in the adaptation process while the execution of the task is done by other parties, either a single agent or a team of agents.

AGENT-BASED COLLABORATIVE PLAN ADAPTATION WITH RESOURCE CONSTRAINTS

Sharing is caring!