This paper describes an approach to scheduling under uncertainty that achieves scalability through a coupling of deterministic and probabilistic reasoning. A class of oversubscribed scheduling problems is considered where the goal is to maximize the reward earned by a team of agents in a distributed execution environment. There is uncertainty in both the duration and outcomes of executed activities, and activities are subject to deadlines. To ensure scalability, the approach takes as its starting point an initial deterministic schedule for the agents, computed using expected duration reasoning. This initial agent schedule is probabilistically analyzed to find likely points of failure, and then selectively strengthened based on this analysis. Experimental results obtained in a multi-agent simulation environment demonstrate that coupling probabilistic and deterministic reasoning in this way results in significantly higher rewards than are achieved by relying on deterministic reasoning alone. In the future, the approach will be extended to include probability-driven meta-level management of execution.

This paper describes aspects of a project aiming at creating general, flexible and reusable software architecture to address planning problems in space missions. It introduces recent work to realize an open software framework for supporting development of planning and scheduling space applications. The framework, which is named TRF (Timeline-based Representation Framework), aims at supporting application development within different space missions for the European Space Agency (ESA). It is currently being tested on three problem examples, all solved on top of the TRF functionalities. This paper describes the TRF three-layered software architecture and shows how it has been used to deploy a complete application, named MrSPOCK, an interactive system for Long Term Planning in the Mars Express operational mission.

This paper presents a project awarded by MGB HK to handle their inspection scheduling problem. MGB HK is the buying office of one of the largest retailers in the world, Metro Group. MGB HK handles all product procurement of Metro Group out of Europe. The inspection process is one of their critical processes along their entire procurement exercise. The objective of this project is to provide an effective scheduling engine so that in-house inspectors can handle as many inspections as possible using the least amount of time and costs. Meanwhile, we also help the company overcome their difficulties of data collection and maintenance as a result of the system we developed. Our engine will be deployed and integrated into the company’s IMS. The engine recorded an improvement in the scheduling of their inspections and initial prognosis indicates that delayed inspections have been greatly reduced by compared with previous schedule. The system can effectively schedule inspections by urgency, shipment value, and supplier’s historical performance. Other than the schedule, the AI engine can also generate solutions based on different strategies and criteria, which facilitate the decision-making process for the scheduling team and management at MGB HK.

Considerable progress has been made over the last 15 years on building adaptive control systems to assist pilots in flying damaged aircraft. Once a pilot has regained control of a damaged aircraft, the next problem is to determine the best site for an emergency landing.  In general, the decision depends on many factors including the actual control envelope of the aircraft, distance to the site, weather en route, characteristics of the approach path, characteristics of the runway or landing site, and emergency facilities at the site.  All of these influence the risk to the aircraft, to the passengers and crew, and to people and property on the ground.  We describe an emergency landing planner that takes these various factors into consideration and proposes possible routes and landing sites to the pilot, ordering them according to estimated risk.   We give an overview of the system architecture and input data, describe our modeling of risk, describe how we search the space of landing sites and routes, and give a preliminary performance assessment for characteristic emergency scenarios using the current research prototype.

We present an implementation of a plan adaptation system, BioPlanner, built for biological pathway prediction across species. BioPlanner formulates a pathway discovery problem as a Hierarchical Task Network (HTN) planning problem and solves it by adapting a plan solution of another well-studied pathway. BioPlanner provides the following functionalities: It automatically builds HTN planning models for a biological pathway domain from the semantic web biological knowledge bases (KBs). It retrieves plan cases from the biological KBs. It generates hypothetical pathways using plan adaptation strategies with the aid of biological domain knowledge. It evaluates the hypothetical plan candidates, ranks them, and recommends the most likely hypotheses to users. It employs an information gathering multi-agent system to capture knowledge from heterogeneous sources to help the hypothetical plan generation process. We utilize BioPlanner to predict Signaling Transduction pathways for Mus musculus, Gallus gallus, and Drosophila melanogaster from Homo sapiens.

The 2008 Robert S. Engelmore Memorial Lecture Award will be presented to Kenneth

Capability planning problems are pervasive throughout many areas of human interest with prominent examples found in defense and security. Planning provides a unique context for optimization that has not been explored in great detail and involves a number of interesting challenges which are distinct from traditional optimization research. Planning problems demand solutions that can satisfy a number of competing objectives on multiple scales related to robustness, adaptiveness, risk, etc. The scenario method is a key approach for planning. Scenarios can be defined for long-term as well as short-term plans. This paper introduces computational scenario-based planning problems and proposes ways to accommodate strategic positioning within the tactical planning domain. We demonstrate the methodology in a resource planning problem that is solved with a multi-objective evolutionary algorithm. Our discussion and results highlight the fact that scenario-based planning is naturally framed within a multi-objective setting. However, the conflicting objectives occur on different system levels rather than within a single system alone. This paper also contends that planning problems are of vital interest in many human endeavors and that Evolutionary Computation may be well positioned for this problem domain.

Surveillance control and reporting (SCR) system for air threats play an important role in the defense of a country. SCR system corresponds to air and ground situation management/processing along with information fusion, communication, coordination, simulation and other critical defense oriented tasks. Threat Evaluation and Weapon Assignment (TEWA) sits at the core of SCR system. In such a system, maximal or near maximal utilization of constrained resources is of extreme importance. Manual TEWA systems cannot provide optimality because of different limitations e.g.surface to air missile (SAM) can fire from a distance of 5Km, but manual TEWA systems are constrained by human vision range and other constraints. Current TEWA systems usually work on target-by-target basis using some type of greedy algorithm thus affecting the optimality of the solution and failing in multi-target scenario. his paper relates to a novel two-staged flexible dynamic decision support based optimal threat evaluation and weapon assignment algorithm for multi-target air-borne threats.

This paper presents a novel two-stage flexible dynamic decision support based optimal threat evaluation and defensive resource scheduling algorithm for multi-target air-borne threats. The algorithm provides flexibility and optimality by swapping between two objective functions, i.e. the preferential and subtractive defense strategies as and when required. To further enhance the solution quality, it outlines and divides the critical parameters used in Threat Evaluation and Weapon Assignment (TEWA) into three broad categories (Triggering, Scheduling and Ranking parameters). Proposed algorithm uses a variant of many-to-many Stable Marriage Algorithm (SMA) to solve Threat Evaluation (TE) and Weapon Assignment (WA) problem. In TE stage, Threat Ranking and Threat-Asset pairing is done. Stage two is based on a new flexible dynamic weapon scheduling algorithm, allowing multiple engagements using shoot-look-shoot strategy, to compute near-optimal solution for a range of scenarios. Analysis part of this paper presents the strengths and weaknesses of the proposed algorithm over an alternative greedy algorithm as applied to different offline scenarios.

Many robotic path planning applications, such as search and rescue, involve uncertain environments with complex dynamics that can be only partially observed. When selecting the best subset of observation locations subject to constrained resources (such as limited time or battery capacity) it is an important problem to trade off exploration (gathering information about the environment) and exploitation (using the current knowledge about the environment most effectively) for efficiently observing these environments. Even the nonadaptive setting, where paths are planned before observations are made, is NP-hard, and has been subject to much research. In this paper, we present a novel approach to adaptive informative path planning that addresses this exploration-exploitation tradeoff. Our approach is nonmyopic, i.e. it plans ahead for possible observations that can be made in the future. We quantify the benefit of exploration through the “adaptivity gap” between an adaptive and a nonadaptive algorithm in terms of the uncertainty in the environment. Exploiting the submodularity (a diminishing returns property) and locality properties of the objective function, we develop an algorithm that performs provably near-optimally in settings where the adaptivity gap is small. In case of large gap, we use an objective function that simultaneously optimizes paths for exploration and exploitation. We also provide an algorithm to extend any single robot algorithm for adaptive informative path planning to the multi robot setting while approximately preserving the theoretical guarantee of the single robot algorithm. We extensively evaluate our approach on a search and rescue domain and a scientific monitoring problem using a real robotic system.