AI Seminar
    -------------------------------
    Tuesday, November 11th, 2003
    4:00 pm - 5:30 pm
    175 ATL (Large Conference Room)

    "Computing the Envelope for Stepwise-Constant Resource Allocations"

    Nicola Muscettola
    Principal Scientist for Autonomy
    NASA Ames Research Center
    mus@email.arc.nasa.gov




----------------------------------
Computing tight resource-level bounds is a fundamental problem in the
construction of flexible plans with activity using variable amount of
resources. In this paper we describe an efficient algorithm that builds
a resource envelope, the tightest possible such bound. At any point in
time an envelope gives the value of the maximum and minimum possible
resource level associated with all possible executions of a flexible
plan. Our algorithm is based on transforming the temporal network of
resource consuming and producing events into a flow network with nodes
equal to the events and edges equal to the necessary predecessor links
between events. A staged maximum flow computation on the network is then
used to obtain the time of occurrence and the height of each step of the
resource envelope profile. Each stage has the same computational
complexity of solving a maximum flow problem on the entire flow network.
This makes this method computationally feasible and promising for use in
the inner loop of flexible-time scheduling algorithms.


Bio:
Dr. Nicola Muscettola is Principal Scientist for Autonomy at the
Computational Sciences Division of the NASA Ames Research Center. Dr.
Muscettola received all his degrees from the Politecnico di Milano,
Milano, Italy. He worked in planning and scheduling research at Carnegie
Mellon University from 1987 to 1993 where he designed the Heuristic
Scheduling Testbed System (HSTS). HSTS demonstrated flexible temporal
planning and scheduling on short-term planning for the Hubble Space
Telescope. In 1993 Dr. Muscettola joined NASA Ames. He was the architect
and project lead for the Planner/Scheduler module of the Deep Space 1
Remote Agent that flew in May 1999. He is the architect of the
Intelligent Distributed Execution Agent, a re-engineering and
rationalization of the Remote Agent architecture, extending it to
multi-agent system with real-time guarantees. In 2003 Dr. Muscettola
received the NASA Exceptional Service Medal for being one of the
principal technologists for the Remote Agent. Dr. Muscettola research
interests are in automated planning and scheduling, temporal and
resource constraint propagation, multi-agent architectures, real-time
control, and validation and testing of autonomous systems.