NEW SPEAKER: Henry Kautz will be unable to give his talk on March 30.
Instead, our speaker will be Anthony Barrett of the University of
Washington.

TIME CHANGE: The seminar will be held at **1:30 pm** instead of 10:30 am.

                            ISI AI Seminar
                       Thursday, March 30, 1995
                               1:30 pm
                 11th Floor West Conference Room, ISI

              FRUGAL HIERARCHICAL TASK-NETWORK PLANNING

                       Anthony Craig Barrett
              Dept. of Computer Science and Engineering
                      University of Washington
                     <barr...@cs.washington.edu>

A hierarchical task-network (HTN) planner takes a partially ordered set of
tasks and actions, and uses schemata to reduce tasks by substituting them
with networks of tasks and actions until only actions remain.  When tasks
and actions interfere with each other, critic functions perform arbitrary
plan-transformation repairs.  A frugal HTN planner takes a goal with the
initial partially ordered set and removes actions that do not contribute
toward the goal.  Not only does this approach to HTN planning produce plans
without superfluous actions, but it facilitates planning with an expressive
action and task representation language containing universal quantification
and conditional effects.

Drawing on recent results from partial-order planning and HTN planning, I
will present and compare two related frugal HTN planners. Unlike previous
HTN planners, both algorithms use an expressive task and action
representation language.  The first algorithm, called UCPARSE, uses a plan
parsing approach to task-decomposition.  While adding actions and orderings
to attain a problem's goals, it uses an incremental parsing algorithm to
recognize when a partially ordered set of actions matches the problem's
tasks.  The second algorithm, called UCREDUCE, extends the reduction
approach to substitute a task with only those tasks and actions (from a
schema) that are needed to attain a problem's goals.  Neither algorithm
dominates the other in all domains, and I will describe those problem
features that lead to one planner dominating another.

--------------------------------------------------

Upcoming Seminars:
------------------

Apr 13  Brian Harp, USC/ISI
        "A FAST trip on the Information Highway: Dirt Roads
         and Six Lane Freeways"

Apr 27  David Wilkins, SRI
        (title TBA)

May 11  Craig Knoblock, USC/ISI
        "Planning, Executing, Sensing, and Replanning for
         Information Gathering"

Sheila Coyazo                 USC/Information Sciences Institute
<scoy...@isi.edu>             4676 Admiralty Way
310/822-1511 x328             Marina del Rey, CA 90292