We present a partial-order, conformant, probabilistic planner, Probapop which competed in the blind track of the Probabilistic Planning Competition in IPC-4. We explain how we adapt distance based heuristics for use with probabilistic domains. Probapop also incorporates heuristics based on probability of success. We explain the successes and difficulties encountered during the design and implementation of Probapop.

Planning algorithms designed for deterministic worlds, such as A* search, usually run much faster than algorithms designed for worlds with uncertain action outcomes, such as value iteration. Real-world planning problems often exhibit uncertainty, which forces us to use the slower algorithms to solve them. Many real-world planning problems exhibit sparse uncertainty: there are long sequences of deterministic actions which accomplish tasks like moving sensor platforms into place, interspersed witha small number of sensing actions which have uncertain outcomes. In this paper we describe a new planning algorithm, called MCP (short for MDP Compression Planning), which combines A* search with value iteration for solving Stochastic Shortest Path problem in MDPs with sparse stochasticity. We present experiments which show that MCP can run substantially faster than competing planners in domains with sparse uncertainty; these experiments are based on a simulation of a ground robot cooperating with a helicopter to fill in a partial map and move to a goal location.

The 2004 International Planning Competition, IPC-4, included a probabilistic planning track for the first time. We describe the new domain specification language we created for the track, our evaluation methodology, the competition domains we developed, and the results of the participating teams.

The AAAI-05 workshops were held on Saturday and Sunday, July 9-10, in Pittsburgh, Pennsylvania. The thirteen workshops were Contexts and Ontologies: Theory, Practice and Applications, Educational Data Mining, Exploring Planning and Scheduling for Web Services, Grid and Autonomic Computing, Human Comprehensible Machine Learning, Inference for Textual Question Answering, Integrating Planning into Scheduling, Learning in Computer Vision, Link Analysis, Mobile Robot Workshop, Modular Construction of Humanlike Intelligence, Multiagent Learning, Question Answering in Restricted Domains, and Spoken Language Understanding.

We provide an overview of the organization and results of the deterministic part of the 4th International Planning Competition, i.e., of the part concerned with evaluating systems doing deterministic planning. IPC-4 attracted even more competing systems than its already large predecessors, and the competition event was revised in several important respects. After giving an introduction to the IPC, we briefly explain the main differences between the deterministic part of IPC-4 and its predecessors. We then introduce formally the language used, called PDDL2.2 that extends PDDL2.1 by derived predicates and timed initial literals. We list the competing systems and overview the results of the competition. The entire set of data is far too large to be presented in full. We provide a detailed summary; the complete data is available in an online appendix. We explain how we awarded the competition prizes.

Despite recent progress in AI planning, many benchmarks remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present and compare two automated methods that learn relevant information from previous experience in a domain and use it to solve new problem instances. Our methods share a common four-step strategy. First, a domain is analyzed and structural information is extracted, then macro-operators are generated based on the previously discovered structure. A filtering and ranking procedure selects the most useful macro-operators. Finally, the selected macros are used to speed up future searches. We have successfully used such an approach in the fourth international planning competition IPC-4. Our system, Macro-FF, extends Hoffmann's state-of-the-art planner FF 2.3 with support for two kinds of macro-operators, and with engineering enhancements. We demonstrate the effectiveness of our ideas on benchmarks from international planning competitions. Our results indicate a large reduction in search effort in those complex domains where structural information can be inferred.

We describe the application of plan-recognition techniques to support human intelligence analysts in processing national security alerts. Identifying intent enables us to both prioritize and explain alert sets to analysts in a readily digestible format. Our empirical evaluation demonstrates that the approach can handle alert sets of as many as 20 elements and can readily distinguish between false and true alarms. We discuss the important opportunities for future work that will increase the cardinality of the alert sets to the level demanded by a deployable application.

We describe the application of plan-recognition techniques to support human intelligence analysts in processing national security alerts. Our approach is designed to take the noisy results of traditional data-mining tools and exploit causal knowledge about attacks to relate activities and uncover the intent underlying them. Identifying intent enables us to both prioritize and explain alert sets to analysts in a readily digestible format. Our empirical evaluation demonstrates that the approach can handle alert sets of as many as 20 elements and can readily distinguish between false and true alarms. We discuss the important opportunities for future work that will increase the cardinality of the alert sets to the level demanded by a deployable application. In particular, we outline the need to bring the analysts into the process and for heuristic improvements to the plan-recognition algorithm.

We are pleased to publish this special selection of articles from the Sixteenth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-04), which occurred July 27-29, 2004 in San Jose, California. IAAI is the premier venue for learning about AI's impact through deployed applications and emerging AI technologies. Case studies of deployed applications with measurable benefits arising from the use of AI technology provide clear evidence of the impact and value of AI technology to today's world. The emerging applications track features technologies that are rapidly maturing to the point of application. The seven articles selected for this special issue are extended versions of the papers that appeared at the conference. Four of the articles describe deployed applications that are already in use in the field. The other three articles, which are from the emerging technology track, were selected because they are particularly innovative and show great potential for deployment.

This article surveys previous work on combining planning techniques with expressive representations of knowledge in description logics to reason about tasks, plans, and goals. Description logics can reason about the logical definition of a class and automatically infer class-subclass subsumption relations as well as classify instances into classes based on their definitions. Descriptions of actions, plans, and goals can be exploited during plan generation, plan recognition, or plan evaluation. These techniques should be of interest to planning practitioners working on knowledge-rich application domains. Another emerging use of these techniques is the semantic web, where current ontology languages based on description logics need to be extended to reason about goals and capabilities for web services and agents.