Action Planning in Sensible Agent-based Systems

Introduction

   Each agent holds some set of desires it wishes to satisfy, as well as limited capabilities (e.g. actions and resources) with which to achieve them.  Since each agent has only limited capabilities to effect changes on the system, agents have to balance the costs of their actions against their desired end.  Thus, the means (plan) by which an agent attains its desired ends (goals) are also important.

    One strength of multi-agent systems is the ability of agents to aid each other in attaining their respective desires.  Collaboration among agents for action selection consists of (1) negotiating a collective desire that the group will strive to attain, (2) deliberation on the possible future outcomes and the effects of agent actions on those outcomes, and (3) selection of the best actions to perform to attain the outcome best matching the collective desire.  Collaboration among agents requires agents to represent and communicate their capabilities and desires so those capabilities and desires can be incorporated in the agents’ decision-making and action selection processes.

    For any given problem, various strategies may be available. We examine the use of coordination mechanisms such as negotiation, voting, arbitration, and self-modification to control the planning process. Each strategy has benefits and drawbacks for their ability to reach a coordinated solution, as measured in terms of message bandwidth used, computational resources used, and the quality of the solution. Given that no single strategy is best for all situations, agents may be equipped with the ability to perform meta-level reasoning about strategy selection for each problem they are addressing.

    In addition to having the capability to interact with other agents in the problem solving process, the reasoning processes contained within each agent must be able to address problems with features prevalent in multi-agent systems. Agents must be able to plan for multiple goals as the agent may take on responsibility for other agent’s goals and dynamic environments, as there are multiple actors in the system, which may not be controlled by the agent. The planning process must understand the capabilities of other agents and the manner in which their actions may interact.

Coordinating Planning Among Agents

    Given that Sensible Agents can dynamically change their organization structure, the agents should be equipped with the ability to change coordination techniques to match.  Encapsulation and polymorphism provide appropriate and  relevant concepts with which to address this ability.   Encapsulation minimizes the interdependencies between objects through intelligent selection of object boundaries.  Encapsulation of the agent coordination mechanism as a strategy separates it from the rest of the infrastructure that composes the agent, such as the manner in which sensing,  modeling, and actuation are implemented as well as other reasoning processes that the agent may perform, including the actual planning process. Polymorphism allows objects that satisfy the same interface to be interchangeable. This allows the meta-level reasoning process plug in the strategy that is most appropriate for any given situation.

Planning Within an Agent

    Effective plan specification, solution extraction and execution are critical to the ability of agent-based systems to operate given the dynamism and uncertainties that exist in real-world domains. Our current research seeks to extend the planning-as-satisfiability model to include the use of symbolic model checking tools from the formal verification community. Symbolic model checking can provide agent-based planners with new capabilities while also providing a computational representation of planning domains that may stretch across the various domain description languages in use today. This single, unifying representation can provide new capabilities to agent systems, supporting a synthesis of some of the separate capabilities derived from other domain description languages or an entirely new set of capabilities that can only be realized using this single AP1.gif (2734 bytes) representation.  Among other capabilities, the developed planner will be able to support the specification of complex goal conditions using Computation Tree Logic (CTL) and will leverage this new information to support the notion of stable planning in distributed domains. Several recent advances in the formal verification community directly relate to the difficulties faced by agent-based systems. Specifically, Alternating Temporal Logic (ATL) extends CTL to include explicit partitioning of distributed systems for goal achievement testing. The application of ATL in agent-based systems provides a domain-independent representation and reasoning mechanism for modeling the future behavior of any partition of entities in an agent-based system. This increase in representational expressiveness coupled with the search algorithms available in the formal verification community seeks to improve the ability of agent-based planners to plan in difficult real-world domains.

Planning For Collaboration

    Deliberative agents model system states over time as linear into the past and branching into the future.  Planning provides a means for an agent to predict future system states, depending on known actions that can be performed.  Those actions describe transitions between system states that agents can hypothetically take at future points in time.  Thus, planning can be used to aid the action selection process by determining the expected outcomes for each respective action the agent has at its disposal.  The agent explores the possible future states of the system based on known possible transitions; to evaluate which action best matches the agent’s desires.  This exploration results in a temporal model of the system representing the causal cone of the states reachable from the current state.

    When the environment becomes more dynamic, as when there are multiple agents, the probability that a given plan will remain valid throughout execution decreases due to uncertainty about other agents’ future actions.  Even though the plan generated by an agent may be invalidated, the planning process still yields information about a range of possible future states for the system.  Rather than using only the resultant (invalid) plan for action selection when replanning, the agent can leverage the temporal system model of possible future states (causal cone) that was built through the planning process.  Introducing collaboration requires an agent’s temporal model of the system to be modified before performing action selection against that model.

    In a collaboration group, the actions available for an agent to plan with include the capabilities of collaborating agents as well as the effects of the joint actions of multiple agents.  Capability combination is the incorporation of collaborating agents’ capabilities into the temporal model of the system, expanding the set of reachable system states.  Desire combination is the process of reaching a compromise among the desires of the collaborating agents, forming a single problem for the collaboration group to address.  Incorporating the desires of collaborating agents constrains the set of desired paths through the future states.

Negotiating For Collaboration

    When combining the desires of the collaborating agents into a collective desire, the agents may have to compromise over which individual desires are included.  In assuring fairness, each agent has two concerns, the benefits yielded by working in the collaboration group, and the costs of group membership.  The benefits of being in the collaboration group are measured by the desires group will satisfy.  Not all desires an agent holds are of equal value.  The agent should have some preference ranking of its desires, recording the priorities of the agent.  This guides the agent when making concessions to the group in negotiating the collective desire.  The costs of working in the collaboration group are measured in terms of the actions that the agent is required to perform.  One obvious cost is the usage of consumable resources.  However, even if the performed actions use no consumable resources, performing actions for the collaboration group restricts the timing of actions that may be performed in pursuit of desires agents may retain outside of the collaboration group.  This is an opportunity cost, equal in magnitude to the potential gain that the agent would have attained by acting either independently or in some other collaboration group.  Since each agent is the final authority on the actions that they will execute, the ability to represent, communicate, and reason about capabilities and desires is integral to achieving collaboration in a multi-agent system.
Agents Use Planning to Explore Future System States

Copyright © 2000 by The University of Texas at Austin, The Laboratory for Intelligent Processes and Systems