Distributed Planning

Martti Meri

Imatran Voima Oy

01019 IVO, Vantaa, Finland

martti.meri@ivo.fi

In Seminar on Knowledge Engineering, Fall 1997, Helsinki University of Technology

Abstract

This paper reviews some of the research made in the area of distributed planning. In multi-agent collaborative planning (Chu-Carrol&Carberry96) agents try to establish a shared-plan that all the agents believe will achieve their common goal, and agree to adopt as the means to achieve this goal. The essential requirement is that the agents can propose actions to each other, evaluate these actions and in a collaborative way propose modifications to the actions. Planning is an abstraction level in a unified theory of coordination between intelligent agents (Durfee93). Co-ordination requires knowledge based search through a hierarchical behavior space, which means that there needs to be a distributed search protocol, because the behavior space is distributed to the agents. Semantic meaning of action changes in multiagent environment, as state transformations are result of a possibly complex interaction of concurrent actions with conditional outcomes (Boutilier&Brafman97) . The basic planning algorithms are however applicable with minor modifications. Agents that have a need for privacy follow strategies in the ways they announce things, respond to announcements, and commit themselves. These heuristic strategies effect the communication overhead and the convergence rate in the reaching of agreements.(Sen97). Contractual setting effects planning in many cases. Contract net protocol (Smith80) is one of the classical approaches. For cases where decommitment possibilities are needed, it is impossible to evaluate probabilities for events causing need to decommit, and agents would prefer a system that compensates for the already performed work, leveled commitment contracts can be used (Sandholm&Lesser). It is suggested that leveled commitment contracts (as superset of full commitment contracts) enable more contracts and improve societal good and distribution.  

Introduction

There are several application areas where the need to build distributed systems emerges. Often it is the situation that there exist a number of human organizations that operate in the shared environment. The nature of operation can be collaborative or non-collaborative. In other cases it can be more of a question of other type of intelligent agents than human organizations. Distributed artificial intelligence (DAI) studies systems that operate in a similar type of setting than the human organizations sharing the environment they operate in. In both of the cases the nature of operation dictates somewhat what is shared. There are many separate research disciplines that study related issues producing results that can be utilized in this setting. In the sequel some of these research areas are indicated in connection to the models referenced.

Proposing, Evaluating and Modifying Actions

In multi-agent collaborative planning (Chu-Carrol&Carberry96) agents try to establish a shared-plan that all the agents believe will achieve their common goal, and agree to adopt as the means to achieve this goal.

The model is truly distributed to the degree that interaction between agents takes place on a discourse level. This level captures the communicative actions initiated to achieve mutual beliefs. Agents make proposals on actions and beliefs to be incorporated to the shared plan. Other agents evaluate these proposals and if they find them non-acceptable make modified proposals based on the original proposals.

Above the discourse level there is the belief level that holding the mutual beliefs pursued during the planning process. From the belief-level upwards all the levels consist of two parts; the existing model, consisting of the things that have been agreed upon and the proposed additions, which are inferred from the agents utterances.

Problem solving level captures how the agents are going about constructing the domain plan. On top there is the domain level consisting of the domain plan being constructed to achieve the shared domain goal(s).

Actions are represented in a tree structure where child nodes contribute to the parent nodes. An action can be infeasible, meaning that it can’t be performed. The plan is said to be ill-formed, if a child action does not contribute to its parent action. Plans are evaluated top-down.

Proposed beliefs are represented in a belief-tree. An agent evaluates the belief tree bottom up because acceptance of a proposed belief may be influenced by acceptance of the beliefs represented by its children in the belief tree, which are intended to provide support for the parent belief. However conflict resolution and negotiating are necessary only if the top level proposed beliefs are not accepted since if the agents agree on a particular belief relevant to the domain plan being constructed, it is irrelevant whether they both agree on all the evidence for that belief.

Evaluation results in acceptance or non-acceptance. Collaborative negotiation means that collaborative agent is responsible to respond to conflicts it detects by notifying the other agents of the conflict and attempt to resolve it. Resolving is performed by problem-solving actions. Proposals are modified to a form that will potentially be accepted by both agents. The type of conflict determines which kind of specialization of modification (Modify-proposal recipe) is required:

Correct-Node, a proposed action is infeasible or a proposed belief is not accepted

Correct-Relation, a proposal is ill-formed or an evidential relationship between two proposed beliefs is not accepted

Improve-Action, better generic action is found

Improve-Parameter, better instantiation of a parameter is found

Table 1: Problem-solving recipes for Correct-Node and its specialization Modify-Node (Chu-Carrol&Carberry96) .

The applicability conditions of Correct-Node specify that the action can be only performed when _s1 believes that _node is not acceptable, while _s2 believes that it is. The body of the recipe includes Modify-Node, which by its behalf keeps the non-acceptance of _node by _s1 as invariant. The precondition concerning the non-acceptance of _node by _s2 causes the discourse that aims to change the belief of agent _s2 so that the modification is possible. As a result a recursive modification process can start where agents try to modify each other’s modification proposals.

Efficient dialogue between the collaborating agents depends on proper selection of the focus in the modification process. Good focus is those rejected beliefs that are predicted to affect most quickly the resolving of the top-level rejected belief. In a similar manner agents try to persuade the others to accept modifications by providing justification to the belief. Selecting right persuasive justification again utilizes prediction. Prediction uses belief revision mechanism.

Co-ordination of actions

A more extended model of agents includes long-term responsibilities and inter-agent interaction patterns, possible opportunism, requirement for reactivity, need for resources.

In such an environment co-ordination can be seen as a process that takes place on three abstraction levels: organizational, planning and scheduling (Durfee93). Of these the organizational level is the most abstract and the scheduling the most specialized (concrete). Co-ordination is seen as a search through a hierarchical space of individual and collective behaviors.

The Common Representation for Coordination Hypothesis: Organizations, plans, and schedules have a common representation, but differ in their degree of specificity along different descriptive dimensions.

In partial global planning, an agent represents its anticipated future problem-solving activities as a problem-solving plan. A problem-solving plan would indicate what data the agent expects to be processed when, and what results it anticipates forming as a result. Agents coordinate their individual plans to work as an effective team by exchanging information about the major plan steps they will be taking and the results they are expecting. As an agent receives this information from others, it determines whether it has any local plans to pursue related results, and if so it combines the received information with the summary of its relevant local plan(s) in to a larger, more global plan.

Besides having a domain-level co-ordination structure that specifies the agents’ roles in solving their application problem, the agents have also common knowledge about the meta-level organization that specifies their roles in solving co-ordination problems. The meta-level organization essentially dictates a management control structure in which some agents’ principal contributions are in coordinating the ongoing activities of others.

Partial global planning constrains the generation of plans within organizational bounds, to co-ordinate plans to improve collective performance, and to institute alternative organizations at both the domain and meta-levels to balance competing needs including reducing communication, reducing computation, increasing reliability and increasing responsiveness to unexpected events.

The common representation referred to in the hypothesis above is called behavior. The description of behavior includes the following slots:

What the behavior is trying to achieve

How it is trying to achieve the results

Who is participating

When the behavior is active

Where the behavioral activities are taking place

Why the behavior has been instituted, that is the motivation for pursuing the goals

Instances of behavior are then combined in a linked network, where a behavior is linked to its more abstract and more specialized behavioral instances. Behavioral hierarchy thus represents the composition and decomposition of an enterprise in terms of time, space, goals, means, personnel, and motivation. The behavioral hierarchy hence represents a search space in which agents attempt to find co-ordinated joint behaviors. Different parts of an enterprise will have different pieces of this hierarchy, and communication between sub-organizations should use the proper behavioral representation. Because of the distribution of the space co-ordination amounts to distributed search, which requires a distributed search protocol for communication. Other elements in the unified theory developed (Durfee93) are local search algorithms (generation of alternative behaviors when searching for more co-ordinated group behaviors), Metrics (criteria for evaluating the combinations of behaviors, based on individual or group performance characteristics), Control knowledge and heuristics (focusing of search).

The impact of social sciences can be seen to distributed artificial intelligence (DAI) with similar setting as here as outlined by Durfee93. Some of the areas are: 

• Organizational theory
• Operations research (at least on the scheduling level)
• Management science, sociology, anthropology
• Communication protocols
• Decision theoretic and Game theoretic metaphors
• Contracting (Contract Net Protocol)
• Ecological systems and human discourse

Planning with Concurrent Interacting Actions

 In order to generate plans for agents with multiple actuators or agent teams, there is a need to represent concurrent actions with interacting effects and possibilities to plan these actions. Historically, this has been considered a challenging task that could require a temporal planner. The planner should be able to reason about resources. With simple modifications, the STRIPS action representation language can be used to represent concurrent interacting actions (Boutilier&Brafman97) . Moreover, current algorithms for partial-order planning require only small modifications in order to handle this language and produce coordinated multiagent plans. These results open the way to partial order planners for cooperative multiagent systems.

In addition to the STRIPS action representation, every action has a "concurrent list" that holds a list of action schemata. Intuitively this list specifies which actions can co-occur or cannot co-occur with the given action in order to produce the effects so described. This list is treated much like a set of preconditions, although it refers to concurrently executed actions rather than conditions that must hold prior to execution.

An example (Boutilier&Brafman97) is presented in figure. The precondition is that the agent is holding the side s1 of a table that is raised. There is a non-concurrency condition that no other agent is simultaneously raising the other side of the table. The primary effect is to have the other side of the table down. In addition the conditional effect states that when there is no concurrent lower action of the other side of the table, and there is some object on the table, that object falls to the floor.

Figure 1: The lower action (Boutilier&Brafman97) .

In multiagent setting the semantics of individual action becomes different. It is rather joint-actions that define state transitions.

A concurrent nonlinear plan for n agents consists of a set of action instances with agent arguments that need not be instantiated, together with a set of arbitrary ordering constraints over the actions (i.e. <,>,=,!= ) and usual codesignation and non-codesignation constraints.

Linearization in multiagent environment (n-linearization) includes the feature that if there are any ordering constraints between individual actions in the different joint-actions, then the same ordering constraints concern also the joint actions.

Partial order Multiagent Planning algorithm (POMP) Boutilier&Brafman97developed is a modified version of UCPOP.

The Contract Net Protocol

In his paper (Smith80) Reid G. Smith presents Contract Net Protocol (CNET).

Distributed problem solving is considered as the co-operative solution to problems by a decentralized and loosely coupled collection of knowledge sources (KS), located in a number of distinct processor nodes.

Decentralization means that both control and data are logically and often geographically distributed; there is neither global control nor global data storage. Loosely coupled means that individual KS’s spend most of their time in computation rather than communication.

Smith examines distributed sensing system (DSS). DSS is a network of nodes each having relatively better capabilities to either sensory or processing tasks. Nodes make task announcements, submit bids and award contracts. (Typically sensory nodes announce processing tasks and processor nodes sensory tasks.). Tasks get partitioned and this leads to hierarchical control structure (note that the structure is thus dynamic).

 Table 2: Contract structure and subcontract structure.(Smith80) .

Nodes make binding bids, and queue them in order of them being awarded. A non-pre-emptive scheduler is used in each node. Contracts are represented as data structures consisting of (among other things) a task identifier and a list of subcontract identifiers. At the subcontract level there is a possibility to list predecessors and successors (other subcontracts) for the subcontracted task. While a subcontract will not be announced until its predecessors have been completed, there is no possibility for distributed planning in this hierarchical control structure. One could perhaps argue that the co-ordination in CNET takes place on the organizational level (in terms of Durfee93).

Heuristic strategies

Meeting scheduling: as a resource allocation problem. In Distributed meeting Scheduling (DMS) agents are thought of as having only partial knowledge of system-wide goals. Agents act for human beings as automated scheduling aids. Strategies for communication must balance demands for privacy with demands for quickly converging on meeting times. Privacy leads typically to exchanging less information , while convergence can be sped up by exchanging more information.

The semantics of meeting as an action is quite limited - only duration and resources (agents participating). However the heuristic strategies presented in the paper could be used in more general planning context also.

The research is based on Multistage negotiation protocol (Contry et al.) which is a generalization of the contract net protocol (Smith80).

Announcement strategies determine how a meeting is announced, and usually involve proposing some number of possible times (Sen97). Host can have as a strategy to announce just the time interval best suited to him or alternatively announce a large set of intervals, he considers good.

Bidding strategy determines what information an invitee sends back based on an announcement (Sen97). The basic strategies yes_no and alternatives correspond to cases where bidder just replies if the announced meeting time is suitable or provides a list of nearest time intervals that suit him.

In this seminar paper the commitment strategy is inspected a bit more in detail.

Time intervals can be viable, proposed, blocked, or reserved. Proposed time intervals are naturally selected from the set of viable time intervals for the agent. Blocked and reserved time intervals are both time intervals that have been earlier on proposed by the agent.

Commitment strategies for agents can be committed or non-committed. Committed strategy blocks off proposed time intervals, where as non-committed does not.

Evaluation of availability of agents under different commitment strategies involves combinatorial analysis (see Fig 2).

Figure 2: Equations for commitment strategies (Sen97) .

An agent has under the commitment strategy an expected availability ratio (AR_Committed) if there are r reserved hours and b blocked hours out of the L hours.

Proposed meeting times can overlap with each other producing two types of conflicts:

• Actual: all viable time intervals overlap with reserved time intervals of another meeting
• Preemptive: at least one viable time interval overlaps with a blocked time interval, but does not overlap with any reserved time intervals.

The expected percentage of actual interactions and preemptive interactions (conflicts) is given by Conf_ac and Conf_pr respectively.

The paper (Sen97) argues that there has been relatively little formal study on the effects of simultaneously available distributed tasks on the efficiency and conflict ratios. Even if the emphasis in the paper in on the scheduling and resources level, one would be tempted to assume that the same consideration applies on the organizational and planning levels of Durfee93 model.

Leveled Commitment Contracting Protocol

 In the original Contract Net Protocol, the agent that had contracted out a task could send a termination message to cancel the contract even when the contractee had already partially fulfilled the contract. This was possible because the agents were not self-interested: the contractee did not mind losing part of its effort without monetary compensation.

Contingency contracts, among self-interested agents is an approach that utilizes known probabilistic future events. Often it is however impossible to enumerate the events in advance, the contract value may depend on combination of the events, and sometimes an event is not observable to all of the agents.

 In leveled commitment contracts decommitment penalties can be used to choose a level of commitment. The method requires no explicit conditioning of future events.

Contracting situation is analyzed from two agent's perspective. Contractor pays for a contractee to get a task done. There are two games, first in a contracting game contracts are made based on minimizing and maximaxing contract prices. Outside offers are considered as future events that change the setting. The decommitment game is a subgame of the contracting game in which both players need to take into consideration (besides the contract price) their respective decommitment penalties and best outside offers.

 Table 3: Contract price, decommitment penalties and outside offers (Sandholm&Lesser.

 A subgame in SEQuential Decommitment game is SEQD (Sandholm&Lesser) is presented below:

Figure 3: Equations for sequential decommitting(Sandholm&Lesser) .

Contractee is represented by B and contractor by A. X_dec means decommitment decision of agent X and X_nod means non-decommitment (staying committed). The payoffs are shown on the two last columns on top of the figure. In situation where both decommit, there are two alternative possible agreements that could have been made - either both agents (the first alternative) or neither agent (latter alternative) pays their penalty.

Here we are only briefly taking a look at the starting position of the sequential decommitment game there are other games havin other positions).

 If the contractee has decommitted, the contractor's best move is not to decommit because -a˘ - a + b ≤ -a˘ + b (because a ≥ 0).

If the contractee has not decommitted, the contractor's best move is to decommit if -a˘ - a ≥ - ρ.

This happens with probability

Put together, the contractee gets b˘ -b if it decommits, b˘ + a if it does not but the contractor does, and ρ if neither decommits. Thus the contractee decommits if

It can be shown that full commitment contracts are a subset of leveled commitment games. Contractor considers equation if -a˘ - a ≥ - ρ and contractee equation ρ < b˘ - b . If a˘ is bounded from below penalty a can be chosen high enough to guarantee commitment. (If b˘ is bounded from above high enough b keep contractee committed.)

The results from the games investigated (Sandholm&Lesser) suggest that it is worthwhile from a contract enabling and contract Pareto efficiency (societal efficiency and disrtibution) improving perspective to incorporate the decommitment mechanism into automated contracting protocols.

Conclusions

As modeled by Durfee (Durfee93), planning is considered as a middle layer having the layer of organizational structure above it and the layer of scheduling below it. Many of the disciplines and metaphors outlined in Durfee's paper are present in the other papers referred. In addition to the coordination layers this review seems to suggest, that there is also a general logical order (or cycle) in which planning takes place.

In each of the approaches there seems to be an action life cycle. First somebody needs to perform a sensory and data fusion type of actions, then there needs to be local reasoning about what needs to be done in the situation (reactive and generative nature of this varies). There must be a mechanism to partition the task so that parts can be proposed to other agents. There must be a way to evaluate proposals, modify them, and get committed (and to even decommit in some cases). 

In the early phases of planning the epistemic considerations are strong. Things are believed locally, outspoken, believed at the receiving end, established as facts. Chu-Carrol&Carberry96 describe a model of knowledge levels.

In the coordinating phases the richness of the elementary action semantics provides the means for coordination. In multiagent environment with actions that set conditions to each others start and continuation, it becomes cumbersome to talk about actions as transformations to the domain state, because these are cross effects of a set of actions performed by several agents (Boutilier&Brafman97).

The organizational scope can vary from a simple non self-interested agent to a complex social organization. At certain level, subjective utilities and self-interest are driving forces. The strategy analysis of (Sen97) shows that announcement, bidding, and commitment can happen by changing varying amounts of information, and this effects the overall efficiency of negotiation. As the complexity increases and overall performance in long run becomes an issue, some system level (Pareto- ) efficiency considerations are introduced (Sandholm&Lesser).

References

Edmund H. Durfee (1993). Organizations, Plans, and Schedules: An Interdisciplinary Perspective on Coordinating AI Systems. Journal of Intelligent Systems, Special Issue on the Social Context of Intelligent Systems, 3(2-4).

Chu-Carrol J., S. Carberry (1996). Conflict Detection and Resolution in Collaborative Planning. Appeared in Agent Theories, Architectures, and Languages, II, Springer-Verlag Lecture Notes.

Sen S. and E.H. Durfee (1997). A Formal Study of Distributed Meeting Scheduling. Group Decision and Negotiation, to appear 1997

Wilkins D.E., K.L. Myers, M. desJardins, P.M. Berry (1997). Summary of Multiagent Planning Architecture, Working document, SRI Project 7150, Stanford research Institute.

Boutilier C., Brafman R. I. , Planning with Concurrent Interacting Actions. Proc. 14th National Conf. on AI (AAAI-97), August 1997.

Sandholm T. W. , Lesser V. R. (1995). Advantages of a Leveled Commitment Contracting Protocol. Extended version. University of Massachusetts at Amherst, Computer Science Technical Report TR 95-72.

Reid G. Smith, The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver. IEEE Transactions on Computers, Vol. C-29, NO. 12, December 1980.