---

Intelligent Workflow for Collection Management

A research project funded by DARPA Solicitation BAA 97-05-PKPX, Advanced Intelligence, Surveillance and Reconnaissance Management.

Dr. Pauline M. Berry

Project Web Page: http://www.ai.sri.com/~swim/

Team Members and Technical Backgrounds

Dr. Pauline M. Berry (SRI-Computer Scientist)

• Voice: (650) 859 2159
• Fax: (650) 859 3735
• Email: berry@ai.sri.com
• Technical Background: Scheduling, Uncertainty, AI Multi-agent Problem Solving Approaches to Management of Information
• Systems: PRS and MPA

Dr. Brian Drabble (CIRL-Research Associate)

• Voice: (541) 346 0473
• Fax: (541) 346 0474
• Email: drabble@cirl.uoregon.edu
• Technical Background: Intelligent Planning, Constraint- Based Search, Intelligent Workflow Generation, Information Modeling
• Systems: O-Plan

Dr. David Wilkins (SRI-Senior Computer Scientist)

• Voice: (650) 859 2057
• Fax: (650) 859 3735
• Email: wilkins@ai.sri.com
• Technical Background: Plan Generation and Execution, Agent Architectures, Knowledge Representation, Problem-Solving
• Systems: SIPE-2, MPA, OAA and KQML

Company POCs

SRI

Ray Perrault (AIC Director)

• Voice: (650) 859 5288
• Fax: (650) 859 3735
• Email: perrault@ai.sri.com

John Lowrance (Program Director)

• Voice: (650) 859 5288
• Fax: (650) 859 3735
• Email: lowrance@ai.sri.com

CIRL

David Etherington (Director & Senior Research Associate)

• Voice: (541) 346 0472
• Fax: (541) 346 0474

Overview

• Motivation (Project Rational)
• Objective/Scope
• Technical Overview
• Technologies
• Scenario Presentation
• SOW Tasks and CDRLs
• Schedule
• Program Plan
• Concerns/Issues
• Draft Outline for May Meeting

Motivation (Project Rational)

• ISR Management Requirements
  • Effective management of ISR assets
  • Satisfaction of complex set of information requirements (strategic/operational)
  • Timely delivery of information
• Research Issues
  • Information Flows - key information resources
  • Agent Capabilities - effective task delegation
  • Reactive & Flexible Agent Tasking

Agenda Driven Workflow Architecture: Key Components

Objectives/Scope

• capture information flows between agents
• model the individual agent (or agent clusters) capabilities
• allow rapid replanning and load balancing necessary for reactive and flexible agent tasking

Technical Approach

• Information Flow Modeling
• Agent Capabilities Modeling
• Workflow Allocation Strategies
• Development/Evaluation Framework

Information Flow Modeling

• Points in the process flow at which information is:
  • created
  • read
  • updated
  • authorized
• The CRUA matrix allows complex dependency recording
  • "You can begin the weaponeering assessment as soon as you have a recommended target list but do not complete this step until the target list has been accepted."

Process Product Attributes

• The products of the process have defined attributes, e.g.
  • review
  • status
  • approval
  • states
  • issue
  • status
  • availability
  • contents level
• The attributes have a number of defined values
  • issue status:
    proposed, current, unreleased, released, published, issued

Information Sources

• From the example,
  • who generated the target list?
  • who is responsible for getting it approved?
• The list came from the "target meeting" step
• The list will be approved at the outcome of the "JGAT meeting" step.
• By understanding the attributes and their potential values it becomes possible to provide better coordination":
  • "Do you have a recommended target list?"
  • "I have the approved one from yesterday and the JGAT meeting to approve today's should finish by 18:00 hrs"

Issues involved in an agent-based architecture

• Agent Topology
  • natural topology of the ISR Domain
  • stability of the topology
• Agent Connectivity
  • the nature, scale and volatility of connections
  • use made of connections
• Interdependence amongst decomposed sub-problems
• Homogeneity or heterogeneity of agents in the process

Agent Capabilities Modeling

• The agents have specific capabilities which allow them to be mapped to steps in the process.
• The capabilities are:
  • dynamic and vary over time
  • related to experience
  • penalties for "overloading" an agent
• The agent capabilities should be modeled in the same terms as the process steps
• The V/N/Q model can be used for both.

Workflow Breakdowns

Schema Phase1-JFACC-Planning
	vars ?dst1 = ?{type agent}, ?dst2 = {type agent}, ?dst3 = ?{type agent}, 
             ?dst4 = {type agent},  ?dst5 = {type agent}, ?dst6 = ?{type agent};
expands {agenda-issue ?src ?dst1 Develop {JFACC-plan} { } };

	
nodes
  1  action {ag-issue O-Plan-WFM ?dst2 Support (developing_objectives} { }},
  2  action {ag-issue O-Plan-WFM ?dst3 Develop (recommended_defense} { }},
  3  action {ag-issue O-Plan-WFM ?dst4 Develop (recommended_apportionment} { }},
  4  action {ag-issue O-Plan-WFM ?dst5 Develop (recommended_target} { }},
  5  action {ag-issue O-Plan-WFM ?dst6 Approve (JFACC_guidance} { }};
end_schema;

Agenda Driven Architecture

• explicit model of tasks to be solved
• explicit model of interdependencies between tasks
• explicit representation of relationships between requirements at different levels of abstraction
• natural correspondence with AIM tasks

Technologies

• VNQ (Verb/Noun/Qualifier)
  to model interagent interactions and agent capabilities
• Constraint Reasoning/Capacity Modeling
  to provide advance load balancing for task allocation
• MPA/PRS
  to provide the technological framework for implementing the manager and testing it within a agent architecture of diverse and distributed capabilities

VNQ (Verb/Noun Phrase(s)/Qualifier Phrase(s))

• Developed to model workflow in ACP domainVerbs describe actions to be performed
  e.g. prioritize, publish, assign
• Nouns phrases describe products of the process on which the action is to be performed
  e.g. target list, weaponeering assignment
• Qualifier phrases provide information on "how" to perform the action
  e.g. broadly, roughly

VNQs in the ISR domain

• supports
  • hierarchical planning
  • libraries of alternative workflow breakdowns
  • the modeling of agent capabilities
    e.g. An agent could refine/build Information Needs (IN) lists
• modeling of constraints in AIM domain
• allows development of an advanced triggering language

Constraint Reasoning/Capacity Modeling

• Requirements
  • Agent Tasking (availability, capability, capacity)
  • Reactive (changes in world or objectives)
  • Resource allocation in the face of incomplete plans
• Technology
  • highly dynamic CSP
  • adaptive constraint satisfaction
  • situation monitoring
  • capacity analysis

Adaptive Constraint Satisfaction

• Components
  • A set of CSP algorithms
  • A set of situation monitors
  • A Strategic Reasoning system
• Approaches
  • Changing the search algorithm (reactive)
  • Changing Search Algorithm (opportunistic)

PRS

What is PRS?

• a framework for building reactive controllers
• smoothly integrates goal- and event-based activities
  • Goal-based behavior: send a robot to target location
  • Event-based behavior: respond to unexpected obstacles
• supports distributed problem-solving through multiple, communicating
• agentsmetalevel reasoning for defining complex control strategies

PRS - (history slide)

A PRS Agent

MPA

What is MPA?

• An architecture for planning/scheduling problems that require collaboration of diverse, distributed agents.
• Enables application of specialized knowledge and technologies to large planning problems
• Facilitates reimplementing and reconfiguring of planning systems
• Support for programming a community of agents to solve a complex planning problem, including producing multiple alternative plans

MPA - Inside a Planning Cell

MPA - Multiple Planning Cells

MPA - Communication

• KQML (Loral and UMBC)
  • PROS: high-level support for declaring and invoking agents, robust
  • CONS: not CORBA-compliant, low-level inefficiencies
• ILU (Xerox PARC)
  • PROS: CORBA-compliant, efficient
  • CONS: no high-level agent support
• OAA (SRI International)
  • PROS: many platforms, many AI and NL applications, tools for creating agents
  • CONS: not CORBA-compliant, Prolog, undocumented

Scenarios

• The workflow will be developed from a number of different perspectives
• The description is similar to the Dynamic Execution Orders (DEO) ideas of Col Buster McCrabb (USAF C2 Directorate)
• The scenario is from an ACP domain but shares many of the characteristics of the ACCM domain

Workflow Task Specification

• A task specifies an activity to be carried out by an agent:
  • Destroy the bridge at coordinate X,Y =>
    aircraft and weapon load
  • Drop food pallets at the following location =>
    aircraft and a series of food pallets
  • Capture ISR data on the follow area =>
    aircraft and a series of collection instruments
• The task assumes that there will be a series of support packages
  • AWACS
  • F-15
  • Tankers
  • NET, NLT

Workflow Information Flows

• How does the agent know about the options available?
• How does the agent carrying out the task know about the support packages?
• More importantly what information does the agent need and what information is he/she required to produce?
• In order to coordinate the activities of the AWACS, F-15 and tankers there needs to be an exchange of information, the question is what information?

Workflow Description

• Each of the agents has a sequence of task orders which specify the tasks to be accomplished.
• The task orders can be fully or partially defined:
  • Drop food pallets at this location between 18:00 and 19:00 on D+5
  • The 82nd airborne will need resupplying on D+20
• The imprecise nature of the tasks mean the task orders "breathe" during both workflow generation and execution
  • What happens if the AWACS aborts on take off?
  • What happens if the information is not available when requested?

Workflow Description

• In order to allow for this type of reasoning each task order is divided into sub-fields

  Plan:

  How long does it take the agent to "plan" the task (20 minutes)

  Notification to Launch:

  How long from notification can the aircraft be airborne (5 min alert)

  Launch Execute:

  How long to get to the target (40 minutes)

  Execute:

  How long to execute the task (10 minutes)

  Recover/Reconstitution:

  How long to service the aircraft (60 minutes)

Workflow Dependencies

• The workflow contains a number of assumptions
  • The AWACS aircraft should be in the air before the ISR mission takes off
  • The F-15s should also be airborne
• The workflow planner will need to coordinate these activities by routing the correct process products to the tasked agent
  • If missions require a critical resource ensure the logistics people have sufficient notification
  • If problems occur the tasked agents needs to know in a timely manner.

Workflow Dependencies

• If the ISR has not launched then, delay the take-off,
  i.e. increase the notification to launch window
• If the ISR is in route then have the aircraft hold,
  i.e. increase the launch to execute window
• If the ISR has to hold then I need to have a tanker in the air to provide it with fuel.
• ......

Workflow Resource Allocation

The resource allocation will need to deal with

• reallocation
• substitution
• retasking

---

Workflow Issues

• Need to raise the description to the process level, e.g. the people manipulating the data.
• Need to identify the agents and their information needs
• Coordination between the agents collecting the data and those who analyze and publish it.
• Requires a Common Plan Representation to support the multi-perspective workflow generation.

---

SOW Tasks

• Develop an ISR Workflow Process Model
  • set of workflow process tasks
  • a workflow process model
  • and information flow model
• Design and Develop an Agent-Based Workflow Framework
• Develop and Implement Agent-based Workflow Management Algorithms
• Experimentally Evaluate Agent-Based Workflow Management
• Demonstrate Agent-based Workflow in ISR
• Reports and Documentation
• Software

---

CDRLs

• An ISR workflow process model
• An ISR information flow model
• An agent based workflow framework
• Agent-based workflow management algorithms
• Experimental evaluation of agent-based workflow management
• Demonstration of agent-based workflow management in ISR domain

---

Program Schedule

---

Program Plan

• Initial Tasks
  • ISR Information Flow Model
  • ISR Agent Capabilities Model
  • Agent Framework Description
• Tasks for May Completion
  • acquisition
  • outline of VNQ for modeling in AIM domain
  • initial research into CSP algorithms
  • initial research into load balancing techniques

---

Resources, Technology Forums, IRADS

SOFTWARE

• PRS
• MPA
• CYPRESS
• ACT Editor
• GRASPER

---

Issues/Concerns

• Access to information to categorize and model agent capabilities
• Qualitative nature of some agent function and task triggering may be difficult to capture
• Access to Information
• Acquisition

---

Draft Outline for May Presentation

• Motivation
• Objectives
• Scope
• Technologies
• Accomplishments
• Plan of Work
• Issues/Concerns

SWIM Project Page
AI Center Home Page
SRI International Home Page

Pauline M. Berry berry@ai.sri.com

Last modified: 4/10/98