Transcript GTrans: Mixed-Initiative Planning System

IT 803 Spring 2004 – Mixed-Initiative Intelligent Systems – Prof. G. Tecuci
GTrans: Mixed-Initiative
Planning System
by Michael Cox
Reviewed by
Vu Le
Presentation Outline





Introduction to GTrans

Planning as goal transformation.

GTrans: a system using goal transformation
Example of using GTrans in planning
Details of GTrans
Lesson learned
References
2
Typical Planning Models: Search




In AI community, one of the most dominant
models of planning is search, as in Protégé.
Planning consists of searching from initial state to
goal state via sequence of operators.
Pre-cond – Operator(params) – Effect
Example: blockworld
B
C
A
B
C
A
Initial state
B
A
C
B
A
C
C
B
A
Final state (Goal)
3
Typical Planning Models:
Hierarchical Task Decomposition




The other common model
is hierarchical task
decomposition, as in
Disciple.
The planning task is
successively decomposed
into subtasks until they are
elementary tasks.
Find the solutions for
simplest tasks.
Successively compose the
solutions until solution to
the initial task is obtained.
T1
S1
T11 S11 … T1n S1n
T111 S111 … T11m S11m
4
The Alternative Approach:
Planning as Goal Transformation




The “alternative” is to model planning as goal
transformation.
Planning involves moving goals through a problem
space to reach equilibrium between available
resources & constraints of dynamic environment.
This approach is still using search in the
background and hiding all details of search from
user.
The user can steer the goal around the problem
space with the help from system to find the best
possible solutions.
5
Planning as
Goal Transformation

Equilibrium between resource and constraints:
enough resource & constraints are preserved.

Constraints violation




Goal is to deliver package to a recipient at certain address.
Recipient is no longer at that address (constraint violated).
Goal change: return the package to sender.
Not enough resource



Goal is to destroy the bridge.
Not enough dynamites to fulfill the task (not enough resource).
Goal change: to reduce the transportation through the bridge
such as damage part of the bridge.
6
Planning as
Goal Transformation

The motivation of modeling planning as goal
transformation is


Cognitive model of planning as search is not intuitive for
human because
Human planner typically jumps around based on existing
knowledge rather than systematically searches the state
space.
B
C
A
B
C
A
Initial state
B
A
C
B
A
C
C
B
A
Final state (Goal)
7
Planning as
Goal Transformation

The other motivation:


Being able to understand planning details
requires amount of knowledge in planning
technology such as pre-conditions, postconditions and operators with variables bound.
Naïve users feel overwhelmed by details of
planning as search.
8
Presentation Outline





Introduction to GTrans

Planning as goal transformation.

GTrans: a system using goal transformation
Example of using GTrans in planning
Details of GTrans
Lesson learned
References
9
GTrans



Mixed-initiative Planning System.
Using goal transformation approach.
Using Prodigy planning system in backend.
10
Presentation Outline





Introduction to GTrans
Example of using GTrans in planning

Create scenario

Step-by-step demonstration
Details of GTrans
Lesson learned
References
11
Create Scenario






Create scenario is the first step
in planning.
Create scenario loads a
domain and sets up the
objects that belong to domain.
Load domain: Military
File/LoadDomain/Military: A
map comes up with no object.
Map has 2 rivers R1, R2 and

bridges over them. There is a
town & 2 airports.
Goal of this exercise is to
prevent movement across
rivers.
When user loads a domain,
the system offers the relevant
objects in that domain for
user to select.

Military domain: Objects: fighter
12
jets, warships, missiles…
Create Scenario








The map has details but they are just images.
Objects that represent them are needed to interact with
GTrans.
Objects have properties: F15 can destroy only 1 bridge and
can damage any bridge.
Create objects: mobile v.s stationary objects.
Mobile objects are drag-and-drop enabled: airplanes, ships,
people.
Stationary objects are not: bridges, rivers, towns, airports.
This scenario needs F15s to destroy bridges.
Create 5 bridges over 2 rivers, 4 F15s, 1 police, 1 infantry.
13
Set Initial States




Select State/Initial States.
Once the user selects initial
state, the system suggests
lists of initial states
associated with objects.
User can set the state of
objects by right-click on
them.
Examples:



F15_1 is ready
Airport_1 is close to river_2
Bridge_1 enables movement
over River_1
14
Set Goals




Select State/Final States.
System helps set up the goals by
providing lists of goals associated
with objects.
There are 2 ways to set goal:
Right-click on target, a popup menu
with goals associated with objects.
Select the desired goal. Bridge: building
bridge, destroy bridge.

Assign resource such as mobile object
to target object by dragging:


Right-click on target, a list of goals
associated with targets and resources
comes up. Select the desired goal.
Drag F15 to bridge -> goal: destroy
bridge by F15

The goal of this scenario is
to make River_1 impassable

The letter “G” will be
asserted at the target.
15
Run Planner





Click on Planning/Run to start the planner.
There will be some types of message returned
from planner such as: Done or No Plan with
explanations.
No plan to blow up all 5 bridges with 4 F15s.
Need goal transformation.
System helps user transform the goal by offering a
hierarchical trees of predicates in particular
domain.


is-destroyed  is-damaged
Impassable  restricted-movement.
16
Transform Goal



Click on Planning/Change Goals to start the transform.
Select current goal and change it.
Change from “outcome-impassable” to “outcome-restrictmovement”.
17
The Final Plan
18
Presentation Outline



Introduction to GTrans
Example of using GTrans in planning
Details of GTrans








Architecture
Communication
Control
Shared awareness
Tasks
Evaluation
Lesson learned
References
19
Architecture
RMI
KQML
• Three-layer architecture:
GTrans RMI server
Planning user interface (PUI)
Prodigy/Agent
20
Architecture





GTrans RMI server and Planning UI use RMI
mechanism to communicate.
Planning UI and Prodigy/Agent use KQML to
exchange information.
GTrans server allows multiple users to co-plan.
Planning UI coordinated with Prodigy/Agent allows
users to create objects, set or modify goals, solve
problems…
Prodigy/Agent allows underlying Prodigy to
communicate with Planning UIs.
21
GTrans Server




Users log in/out to/from
GTrans server during planning.
A user shares planning
information to other users via
GTrans server in joint/share
planning mode.
The user uses PUI to
communicate with system.
The interactions of Gtrans server and Planning UIs
follows publisher-subscribers pattern.


A PUI subscribes to the publisher (GTrans server) when user logs
in to the system.
An event generates from PUI will be distributed to subscribed
22
PUIs via publisher.
Planning User Interface (PUI)



This is the user’s workplace where menu-based mixedinitiative transactions happen.
Users can setup goals, assign resources, change goals with
agent assistance.
There are two types of transactions from Planning UI


To GTrans Server: RMI
To Prodigy/Agent: KQML
23
Prodigy/Agent





Consists of Prodigy Planner and wrapper
Prodigy Planner is a domain independent,
state-space planner.
Prodigy uses backward & forward search
from initial states to goal.
Prodigy domains are represented with a
conceptual hierarchy and a set of operators.
Wrapper serves as interface between
Prodigy planner and Planning UI.
24
Presentation Outline



Introduction to GTrans
Example of using GTrans in planning
Details of GTrans

Architecture

Communication






Control
Shared awareness
Tasks
Evaluation
Lesson learned
References
25
Communication

There are 2 types of communication:




Among users
Between user and agent
Communication between users is realized by
GTrans RMI server.
Communication between user and agent is
realized by Prodigy wrapper.
26
Human Users Communication
RMI
KQML
27
Registration Service





GTrans RMI Server offers registration service
Each Planning UI connects to GTrans server
has to register.
Each Planning UI disconnects to GTrans
server has to unregister.
Registration service monitors all connected
clients and allows interaction between
clients.
Planning UI connects to server via Java RMI.
28
Registration Service
subscribe
acknowledge
create event
GTrans RMI
Server
acknowledge
Planning UI
distribute event
acknowledge
unsubscribe

Typical events:




Add objects
Set goals
Set states
Request shared objects





Move objects
Delete objects
Remove goals
Remove states
Release shared objects
29
RMI (Remote Method Invocation)





RMI facilitates the interprocess communication
between Java Virtual Machines.
RMI enables remote method invocation.
RMI server creates the remote objects.
RMI client invokes a method on a remote object.
Example


Naming.bind(“rmi:///CalendarImpl”, new CalendarImpl());
//create an instance of object and bind it to name CalendarImpl
Naming.lookup(“rmi:///cs.gmu.edu/CalendarImpl”);
//lookup the remote object at the specified URI: remote objects
//bound to the name CalendarImpl at cs.gmu.edu
30
Human User & Agent Communication
31
Human User & Agent Communication


The communication is enabled via Prodigy
wrapper.
KQML (Knowledge Query & Manipulation
Language) is used in communication.
 Lisp-like syntax
 (tell :content (word “hello”) :sender M
:receiver S)
 (request :content (kill P))
 (achieve :content (killed P))
32
KQML - Standard Verbs
33
KQML - Standard Parameters
34
Presentation Outline



Introduction to GTrans
Example of using GTrans in planning
Details of GTrans

Architecture
Communication

Control






Shared awareness
Tasks
Evaluation
Lesson learned
References
35
Control Issues (Single Plan)


User sends planning request to
agent via achieve(goals)
If the agent does not fully
understand the context of the goals,
then it asks user via
query(obj,state) such as What is
initial state of the missile?

The clarification is realized by
reply(obj,state)


If everything is clear then agent
generates plan and send back the
plan to user via tell(plan)
If there are more than one available
plans in system then the agent
receives a standby signal. In this
case we have multiple plans
36
Control Issues (Multiple Plans)




When agent receives standby
signal then it asks user if s/he
wants more by ask-one.
The user can cancel or next
next signals agent to provide a
stream of plans.
The first next provides all
needed parameters such as
depth-bound, time-bound…

agent sends back first plan via
tell.


The next next specifies how the
next plan differs from the first
(shorter, different…)
Continue until no more plan
37
Control Issues (Multiple Plans)
38
Presentation Outline



Introduction to GTrans
Example of using GTrans in planning
Details of GTrans

Architecture
Communication
Control

Shared awareness






Tasks
Evaluation
Lesson learned
References
39
Shared Awareness

There are two types of communication:



Among users
Between user and agent.
Consequently, there are two types of shared
awareness:


Shared awareness among users
Shared awareness between user and agent
40
Shared Awareness Among Users

There are 3 modes of planning




Separate planning: Plans cannot be seen by
other planners, all resultant plans are
independent.
Information sharing planning: Plans can be seen
by other planners, all resultant plans are
independent
Joint planning: Plans can be seen by other
planners, all resultant plans combine into a
complex plan.
Share/Joint planning allows shared
awareness to be realized.
41
Separate Planning




The users do not cooperate in separate
planning.
No one can see other’s
plan.
The domains from
different users can be
different.
In short, the two plans
are total independent.
42
Information Sharing Planning





The users do not cooperate in separate
planning.
But one can see other’s
plan.
The domains from
different users can be
different.
In short, the two plans
are total independent.
One of purposes of this
mode is to compare
plans.
43
Joint Planning





The users do co-operate
in planning.
One can see other’s
plan.
The domains from
different users can be
different.
In short, the two
planning are
independent.
Joint planning is really
useful in multi-domains
planning.
44
Joint Planning

Example of joint planning:






Suppose to send a package from a post office to
an oversea country.
One planner has expertise in truck-logistics
domain.
The other planner has expertise in air-logistics
domain.
Neither domain is suffice to carry on the task.
Neither planner can achieve the goal by itself.
Need to joint plan: from post office carry
package by truck to nearest airport. From there
fly the package over to that country.
45
Shared Objects




Ownership of objects: in joint planning the server serves as
repository of objects.
If user wants to borrow objects not owned by her/him then
s/he sends request to server.
If the object is available (either not owned by any one or
owned but not in use) then that object is sharable.
Example:


In military domain, an F15 is defined as being able to blow up only
1 bridge but can damage a numbers of bridges.
If the task is blowing up 2 bridges with only 1 F15 then there are 2
solutions:


Either ask for help by getting 1 more F15 if it’s available.
Or reduce the goal to blow up 1 bridge and damage 1 bridge.
46
Shared Awareness between user and
agent



The agent and user share
information during the
discourse.
The agent sends to user the
info based on request:
All objects in domain.
All available goals in domain.
All initial states in domain.
All hierarchy of concepts,
predicates in domain.
The information helps user
create objects, set initial
states, setup goals, transform
goals.
47
Shared Awareness between user and
agent

All objects in domain: help user select available
objects in domains.


Available goals in domain: help user decide what
goal to achieve.


Associated with bridge is goal of destroying, building…
Initial states in domain: help user setup initial states
of problem.


Fighter jets, warships, missiles… in military domain.
Associated with missiles is state of being stored, loaded…
Hierarchy of concepts, predicates: help user
transform the goal.

Hierarchy of predicates: is-destroyed  is-damaged
48
Presentation Outline



Introduction to GTrans
Example of using GTrans in planning
Details of GTrans

Architecture
Communication
Control
Shared awareness

Tasks

Evaluation





Lesson learned
References
49
Task: User Task





Defining the goals.
Assigning the resources. This is nice feature of Goal
Transformation.



The planning details are
hidden from user in black-box.
The user has 3 handles to the
black-box.
The user controls the planning
process by:
Users has more control over the process.
Set the priorities of goals (not implemented).
Adjusting the goals and resources based on the world
changes as well as the response (succeeded, failed with
explanations) from black-box.
50
Task: Agent Task




Generates the plan based on inputs from
users.
Helps users create objects, setup initial
states and goals (via menus)
Helps users transform the goals.
There are 3 types of goal transformation:



Goal type transformation
Goal argument transformation
Negated goal transformation
51
Goal Type Transformation

Transform a goal by moving the predicate of the
goal along an abstraction hierarchy defined in the
domain knowledge.
is-ineffective
is-isolated




is-destroyed
(is-ineffective enemy-brigade1)
(is-isolated enemy-brigade1) or (is-destroyed enemy-brigade1)
is more specific.
Assume the initial plan is (is-destroyed enemy-brigade1)
The discovery of non-combatants in the battle area necessitates
the change to (is-isolated enemy-brigade1)
52
Goal Argument Transformation

Transform a goal by moving its arguments
along the abstraction hierarchy of objects in
domain knowledge.




Initial goal: (destroyed-by bridge_1 F15_1) The specific
bridge bridge_1 is destroyed by specific F15_1
Transformed goal: (destroyed-by bridge F15) Any
bridge can be destroyed by any F15.
The transformed goal is more generic than initial goal.
When there is not enough resource to fulfill initial goal,
the transformed goal is good enough.
53
Negated Goal Transformation


This type of transformation is to inverse a goal.
Purposes: for what-if scenario


The user may want to see what happens if bridge_1 is not
destroyed by f15_1
Or to annul a particular goal and still want to keep
the planning process going on.


Initial goal: destroy bridge_1 and bridge_2 with only 1
F15_1. => Plan failed
Transformed goal: destroy bridge_2 only (more critical
infrastructure).
54
Presentation Outline



Introduction to GTrans
Example of using GTrans in planning
Details of GTrans

Architecture
Communication
Control
Shared awareness
Tasks

Evaluation






Lesson learned
References
55
Goal Satisfaction as Function of
Cognitive Model







Goal satisfaction is the ratio of actual goal satisfaction
achieved by the participant’s plan to the goal satisfaction
achieved by the optimal plan.
Given a goal to destroy a bridge, destroying it achieves
100% goal satisfaction, damaging it achieves only 50%
goal satisfaction.
The experiment uses 18 variations on the Bridge problem.
Insufficient resources exists.
Uses 2 models: search and goal transformation.
Search model allows partial goal planning.
Goal manipulation lets users transform the goal to achieve
partial goal planning.
56
Goal Satisfaction as Function of
Cognitive Model



Experts are 6 out of 13
subjects who had
familiarity to search in AI.
When presents with goal
manipulation model,
achievement is over 95
percent goal satisfaction
on average.
When presents with search
model, achievement is
about 80 percent goal
satisfaction on average.
57
Goal Satisfaction as Function of
Complexity




Problems with longer plan is considered more
complex than problem with shorter plan.
Complexity is dependent on the number of
steps in the optimal plan.
Uses the same setup as before.
Categorizes 18 problems into 3 categories:



Number of steps ≤ 13: Easy
14 ≤ Number of steps ≤ 25: Medium
26 ≤ Number of steps: Hard
58
Goal Satisfaction as Function of
Complexity


Presents the average goal
satisfaction ratio for
combination of planning
model and problem
complexity.

When the goal
manipulation model is
presented to users, the
goal satisfaction almost
remains the same with
increasing problem
complexity.
When the search model is
presented to users, the
goal satisfaction decreases
when the problem
complexity increases.
59
Goal Satisfaction as Function of
Expertise





Using the same setup as
before.
Presents the average goal
satisfaction ratio for
combination of planning model
and expertise levels.
The experts perform better than the novices in each model.
The goal satisfaction ratio is still higher in goal manipulation
model.
Both lines are not parallel and that means the difference
between novices and experts in goal manipulation model is
less than that of search model.
60
Presentation Outline





Introduction to GTrans
Example of using GTrans in planning
Details of GTrans
Lesson learned
References
61
Lesson Learned

Strength:





Planning becomes easier with visualization.
Hiding all search trees from novices => easier
for them to make decision.
Assigning resources & transforming goals as
needed make planning more understandable.
System helps users in setting up scenario and
goals as well as transforming the goal.
Drag & Drop capability speeds up the planning
process.
62
Lesson Learned

Weakness:





All goals have the same priorities.
In Joint/Share planning modes, all information is
shared. Should share only information which
may interfere the planning.
Mixed-initiative is less interactive and less
explicit.
No appropriate explanation for a planning
failure.
No learning capability.
63
Presentation Outline





Introduction to GTrans
Example of using GTrans in planning
Details of GTrans
Lesson learned
References
64
References









Cox, M. T., Edwin, G., Balasubramanian, K., & Elahi, M. (2001). Multiagent goal transformation and mixedinitiative planning using Prodigy/Agent. To appear in Proceedings of the 5th World Multiconference on
Systemics, Cybernetics and Informatics (SCI 2001). http://www.cs.wright.edu/~mcox/Papers/cox-edwinbalas-elahi.ps
Cox, M., Kerkez, B., Srinivas, C., Edwin, G., Archer, W. (2000). Toward Agent-Based Mixed-Initiative
Interfaces.In H. R. Arabnia (Ed.), Proceedings of the 2000 International Conference on Artificial Intelligence ,
Vol. 1 http://www.cs.wright.edu/people/faculty/mcox/ic-ai/abmii-camera-ready.pdf
Immaneni, T., & Cox, M. T. (2004). GTrans: An application for mixed-initiative collaborative planning during
emergency response situations. In W. W. Smari & W. McQuay (Eds.), Proceedings of the 2004 International
Symposium on Collaborative Technologies and Systems (CTS 04), (pp. 121-126). San Diego: Society of
Modeling and Simulation International. http://www.cs.wright.edu/people/faculty/mcox/Papers/immaneni-cox04.pdf
Veloso, M. M., Mulvehill, A. M., & Cox, M. T. (1997). Rationale-supported mixed-initiative case-based
planning. In Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative
Applications of Artificial Intelligence Conference (pp. 1072-1077). Menlo Park, CA: AAAI Press / The MIT
Press. http://www.cs.wright.edu/~mcox/Ftp/veloso-mulvehill-cox.ps
Zhang, C., Cox, M. T., & Immaneni, T. (2002). GTrans version 2.1 User manual and reference (Tech. Rep. No.
WSU-CS-02-02). Dayton, OH: Wright State University, Departmentof Computer Science and Engineering.
http://www.cs.wright.edu/~mcox/Gtrans/Tech-Rep-WSU-CS-02-02.pdf
Cox, M. T. (2001). Toward tailored information presentation in support of collaborative planning. In B. Bell &
E. Santos (Eds.), Intent Inference for Collaborative Tasks: Papers from the 2001 fall symposium (pp. 44-50).
AAAI Technical Report FS-01-05.Menlo Park, CA :AAAI Press.
http://www.cs.wright.edu/~mcox/Ftp/mcox01.pdf
Cox ,M.T.(2000).A conflict of metaphors :Modeling the planning process.In Proceedings of 2000 Summer
Computer Simulation Conference (pp. 666-671) .San Diego :The Society for Computer Simulation
International. http://www.cs.wright.edu/people/faculty/mcox/Ftp/metapho-camera-ready.pdf
Finin, T., McKay, D., & Fritzson, R. (1992). An Overview of KQML: A Knowledge Query and Manipulation
Language. Computer Science Department, University of Maryland.
http://citeseer.nj.nec.com/chalupsky92overview.html
Zhang, C. (2002), Cognitive Models For Mixed-Initiative Planning. Master’s thesis. Wright State University,65
Dayton, OH. http://www.cs.wright.edu/~mcox/GTrans/zhang2002.pdf
References








Cox, M. T. (in press). Planning as mixed-initiative goal manipulation . To appear in the Proceedings of the
Workshop on Mixed-Initiative Intelligent Systems at the 18th International Conference on Artificial
Intelligence. Menlo Park, CA: AAAI Press. http://www.cs.wright.edu/~mcox/Ftp/cox-ijcai03.pdf
Michael T. Cox, Thomas Hartrum, Scott DeLoach,1 and S. Narayanan. Agent-Based Mixed-Initiative
Collaboration: The ABMIC project final report. Wright State University Technical Report WSU-CS-02-01, July
2002. http://www.cis.ksu.edu/~sdeloach/ai/publications/ABMIC-final.report2.pdf
Cox, M. T., & Veloso, M. M. (1997a). Controlling for unexpected goals when planning in a mixed-initiative
setting. In E. Costa & A. Cardoso (Eds.), Progress in Artificial Intelligence: Eighth Portuguese Conference
on Artificial Intelligence (pp. 309-318). Berlin: Springer. http://www2.cs.cmu.edu/afs/cs.cmu.edu/project/prodigy/Web/Mixed-init/Papers/m-init3.html
Cox, M. T., & Veloso, M. M. (1997b). Supporting combined human and machine planning: An interface for
planning by analogical reasoning. In D. B. Leake & E. Plaza (Eds.), Case-Based Reasoning Research and
Development: Second International Conference on Case-Based Reasoning (pp. 531-540). Berlin: SpringerVerlag. http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/prodigy/Web/Mixed-init/Papers/ui.ps.gz
Cox, M. T., & Veloso, M. M. (1997c). Supporting combined human and machine planning: The Prodigy 4.0
User Interface Version 2.0 (Tech, Rep. No. CMU-CS-97-174). Pittsburgh: Carnegie Mellon University,
Computer Science Department. http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/prodigy/Web/Mixedinit/Papers/ui-tech-rep.ps.gz
Cox, M. T., & Veloso, M. M. (in press). Goal Transformations in Continuous Planning. In M. desJardins (Ed.),
Proceedings of the 1998 AAAI Fall Symposium on Distributed Continual Planning. Menlo Park, CA: AAAI
Press / The MIT Press. http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/prodigy/Web/Mixedinit/Papers/goal-trans.ps.gz
Tecuci, G. Lecture notes of CS785 George Mason University, 2001.
Stanescu, B. Presentation: The Trips system. George Mason University, 2004.
66