Smith, D. E.


The Case for Durative Actions: A Commentary on PDDL2.1

arXiv.org Artificial Intelligence

The addition of durative actions to PDDL2.1 sparked some controversy. Fox and Long argued that actions should be considered as instantaneous, but can start and stop processes. Ultimately, a limited notion of durative actions was incorporated into the language. I argue that this notion is still impoverished, and that the underlying philosophical position of regarding durative actions as being a shorthand for a start action, process, and stop action ignores the realities of modelling and execution for complex systems.


Planning Graph Heuristics for Belief Space Search

arXiv.org Artificial Intelligence

Some recent works in conditional planning have proposed reachability heuristics to improve planner scalability, but many lack a formal description of the properties of their distance estimates. To place previous work in context and extend work on heuristics for conditional planning, we provide a formal basis for distance estimates between belief states. We give a definition for the distance between belief states that relies on aggregating underlying state distance measures. We give several techniques to aggregate state distances and their associated properties. Many existing heuristics exhibit a subset of the properties, but in order to provide a standardized comparison we present several generalizations of planning graph heuristics that are used in a single planner. We compliment our belief state distance estimate framework by also investigating efficient planning graph data structures that incorporate BDDs to compute the most effective heuristics. We developed two planners to serve as test-beds for our investigation. The first, CAltAlt, is a conformant regression planner that uses A* search. The second, POND, is a conditional progression planner that uses AO* search. We show the relative effectiveness of our heuristic techniques within these planners. We also compare the performance of these planners with several state of the art approaches in conditional planning.


Conditional nonlinear planning

Classics

"Work-in-progress on the design of a conditional nonlinear planner is described. CNLP is a nonlinear planner that develops plans that account for foreseen uncertainties. CNLP represents an extension of the conditional planning technique of Warren [75] to the domain of nonlinear planning." In ICAPS-92, pp. 189–197.


Controlling recursive inference

Classics

"Loosely speaking, recursive inference occurs when an inference procedure generates an infinite sequence of similar subgoals. In general, the control of recursive inference involves demonstrating that recursive portions of a search space will not contribute any new answers to the problem beyond a certain level. We first review a well-known syntactic method for controlling repeating inference (inference where the conjuncts processed are instances of their ancestors), provide a proof that it is correct, and discuss the conditions under which the strategy is optimal. We also derive more powerful pruning theorems for cases involving transitivity axioms and cases involving subsumed subgoals. The treatment of repeating inference is followed by consideration of the more difficult problem of recursive inference that does not repeat. Here we show how knowledge of the properties of the relations involved and knowledge about the contents of the system's database can be used to prove that portions of a search space will not contribute any new answers." Artificial Intelligence, 30 (3), 343-89.


An Overview of Meta-Level Architecture

Classics

"One of the biggest problems in AT programming is the difficulty of specifying control. Meta-level architecture is a knowledge engineering approach to coping with this difficulty. The key feature of the architecture is a declarative control language that allows one to write partial specifications of program behavior. This flexibility facilitates incremental system dcvclopment and the integration of disparate architectures like demons, object-oriented programming, and controlled deduction. This paper presents the language, describes an appropriate, and cliscusses the issues of compiling. It illustrales the architecture with a variety of examples and reports some experience in using the architecture in building expert systems."Earlier: M. Genesereth and D.E. Smith. Meta-level Architecture. Memo HPP-81-6, Computer Science Department, Stanford University, 1981.In Proceedings of the AAAI, Washington, DC., August, 1983