Information Technology


Learning to Integrate Reactivity and Deliberation in Uncertain Planning and Scheduling Problems

AAAI Conferences

The AI problem of automatically achieving goals has been redefined in the last few years. The classical planning problem can be broadly characterized as finding a set of operators together with sufficient constraints such that when applied to some initial state the resulting state provably satisfies some goal relation. However, this is a narrow view of what is now seen as a more general problem. Recently, there has been a great deal of interest in reactivity as a model of action [Suchman87]. While the classical view of planning has been shown to have computational problems [Chapman87]; from a different perspective one might instead blame our failure to conceive of alternative frameworks for modeling world changes and formalisms for action selection.


SS92-01-023.pdf

AAAI Conferences

Box 179, ms XL4370 Denver, CO 80201 Abstract A scheduling and resource management system named MAESTRO has been interfaced with a Space Station Module Power Management and Distribution (SSMPMAD) breadboard at Marshall Space Flight Center (MSFC). The combined system serves to illustrate the integration of planning, scheduling and control in a realistic, complex domain. This paper briefly describes the functional elements of the combined system, including normal and contingency operational scenarios, then focusses on the method used by the scheduler to handle real-time contingencies. I. Introduction For the past six years a team at Martin Marietta has been developing an integrated approach to scheduling, resulting in the implementation of a robust prototype scheduling system called MAESTRO [Geoffroy, Gohring & Britt, 1991]. During the same time frame another group at Martin Marietta has been building a hardware/software testbed to study various concepts in the automation of electrical power management, the Space Station Module Power Management and Distribution (SSMPMAD) system.


Scheduling Revisited Workstations in Integrated-Circuit Fabrication

AAAI Conferences

The cost of building new semiconductor wafer fabrication factories has grown rapidly, and a state-of-the-art lab may cost $250 million or more. Obtaining an acceptable return on this investment requires high productivity from the fabrication facilities. This paper describes the Photo Dispatcher system which has been developed to make machine-loading recommendations at a sat of key fab machines. Dispatching policies that generally perform well in job shops (e.g., Shortest Remaining Processing Time) perform poorly for workstations such as photolithography which are visited multiple times by the same lot of silicon wafers. The Photo Dispatcher evaluates the history of workloads throughout the fab and identifies bottleneck areas.


Realization of High Quality Production Schedules Structuring Quality Factors via Iteration of User Specification Processes

AAAI Conferences

This paper describes an architecture for realizing the high quality production schedules. Although quality is one of the most important aspects of production scheduling, it is difficult even for a user to specify precisely. However it is also true that the decision whether a schedule is good or bad can be taken only by a user. This paper proposes; The quality of a schedule can be represented ill the form of quality factors, i.e. constraints and objectives of the domain, and their structure. Quality factors and their structure can be used for decision making at local decision points during the scheduling process. They can be defined via iteration of user specification processes.


Rescheduling with Iterative Repair

AAAI Conferences

This paper presents a new approach to rescheduling called constraint-based iterative repair. This approach gives our system the ability to satisfy domain constraints, address optimization concerns, minimize perturbation to the original schedule, and produce modified schedules quickly. The system begins with an initiM, flawed schedule and then iteratively repairs constraint violations until a conflict-free schedule is produced. In an empirical demonstration, we vary the importance of minimizing perturbation and report how fast the system is able to resolve conflicts in a given time bound. These experiments were performed within the domain of Space Shuttle ground processing. Introduction Monte Zweben Eugene Davis* Brian t Daun Michael Deale$ NASA Ames Research Center M.S. 269-2 Moffett Field, California 94035 Space Shuttle ground processing encompasses the inspection, repair, and refurbishment of space shuttles in preparation for launch.


O-Plan2: The Open Planning Architecture

AAAI Conferences

Brian Drabble, Richard Kirby and Austin Tate Artificial Intelligence Applications Institute University of Edinburgh 80 South Bridge Edinburgh EH1 1HN United Kingdom The O-Plan2 Project at the Artificial Intelligence Applications Institute of the University of Edinburgh is exploring a practical computer based environment to provide for specification, generation, interaction with, and execution of activity plans. O-Plan2 is intended to be a domain-independent general planning and control framework with the ability to embed detailed knowledge of the domain. A hierarchical planning system which can produce plans as partial orders on actions. An agenda-based control architecture in which each control cycle can post pending tasks during plan generation. These pending tasks are then picked up from the agenda and processed by appropriate handlers (Knowledge Sources).


Planning, Scheduling, and Control for Automatic Telescopes

AAAI Conferences

APT there is a single person who acts as a central clearinghouse for usage requests; such a person is known in the vernacular as the APT's principal Astronomer, or PA. Thus, once an astronomer has assembled his or her set of ATIS groups, they package the groups off to the appropriate PA. The PA collects together such sets from a variety of astronomers, attempts to ensure that the telescope is not overloaded, and then sends the complete set of groups off to the correct telescope. Actual communication between PA and APT is carried out by using personal computers, moderns, and phone lines, but the particular technology isn't critical for the current discussion. The important aspect of the communication is that the PA can be located anywhere on the planet (in principle), and need only have access to an appropriate communication link.


Real-time Scheduling Using Minimin Search

AAAI Conferences

In this paper we described a real-time scheduling system based on the Minimin algorithm and showed that it is effective and capable of producing good schedules with reasonably small effort. In particular, we showed that the schedule quality improves with increased lookahead, confirming some of the results of Korf on Realtime Search in the scheduling domain. The future work includes evaluation function learning, variable depth searches, and demonstration of the reactivity of the system. Although much remains to be done, the preliminary results reported in this paper appear promising.


Bhaskar Janakiraman and Armand Prieditis Department of Computer Science University of California Davis, CA95616

AAAI Conferences

A project scheduling problem consists of a finite set of jobs, each with fixed integer duration, requiring one or more resources such as personnel or equipment, and each subject to a set of precedence relations, which specify allowable job orderings, and a set of mutual exclusion relations, which specify jobs that cannot overlap. No job can be interrupted once started. The objective is to minimize project duration. This objective arises in nearly every large construction project--from software to hardware to buildings. Because such project scheduling problems are NPhard, they are typically solved by branch-and-bound algorithms.


Experiments with a Decision-Theoretic Scheduler

AAAI Conferences

Scheduling problems arise in schools, in factories, in military operations and in scientific laboratories. Although many algorithms have been proposed, scheduling remains among the most difficult of optimization problems. Because of the problem's ubiquity and complexity, small improvements to the state-of-the-art in scheduling are greeted with enormous interest by practitioners and theoreticians alike. A large class of scheduling problems can be represented as constraint-satisfaction problems (CSPs), representing attributes of tasks and resources as variables. Task attributes include the scheduled time for the task (start and end time) and its resource requirements.