Recent Papers by David E. Wilkins

Address: SRI International E-Mail:
333 Ravenswood Ave.
Menlo Park, CA 94025
USA

David E. Wilkins, Stephen F. Smith, Laurence A. Kramer, Thomas J. Lee, Timothy W. Rauenbusch, "Airlift mission monitoring and dynamic rescheduling", available online as of May 2007 (doi:10.1016/j.engappai.2007.04.001), Engineering Applications of Artificial Intelligence Journal, March, 2008, volume 21, number 2, pp. 141-155

David E. Wilkins, Grit Denker, Mark-Oliver Stehr, Daniel Elenius, Rukman Senanayake, and Carolyn Talcott,
"Policy-Based Cognitive Radios", IEEE Wireless Communications, Special Issue on Cognitive Wireless Networks, volume 14, number 4, pp. 41-46, August 2007.

Abstract: We present a new language for expressing policies that allow opportunistic spectrum access while not causing interference. CoRaL has expressive constructs for numerical constraints, supports efficient reasoning, and will be verifiable. The language is extensible so that unanticipated policy types can be encoded. We also describe a Policy Reasoner that reasons about CoRaL policies, and show how this reasoner can be used with various cognitive radios (in this case, an XG radio) to guarantee policy-specified behaviors while allowing spectrum sharing.

Grit Denker, Daniel Elenius, Rukman Senanayake, Mark-Oliver Stehr, David Wilkins,
"A Policy Engine For Spectrum Sharing", in New Frontiers in Dynamic Spectrum Access Networks, 2nd IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN), April 2007, pp. 55-65.

Abstract: We argue for a policy-based approach to increase spectrum availability. We summarize a new language for expressing policies that allow opportunistic spectrum access. A Policy Reasoner that reasons about these policies can be used with cognitive radios to guarantee policy-specified behaviors while allowing spectrum sharing. We evaluated the reasoner in a demonstration. We describe the policies used in that demonstration and the results of the evaluation.

David E. Wilkins, Stephen Smith, Larry Kramer, Thomas J. Lee, and Tim Rauenbusch,
"Execution Monitoring and Replanning with Incremental and Collaborative Scheduling", ICAPS 2005 Workshop on Multiagent Planning and Scheduling, Monterey, CA, 2005.

Abstract: We describe the Flight Manager Assistant (FMA), a prototype system, designed to support real-time management of airlift operations at the USAF Air Mobility Command (AMC). In current practice, AMC flight managers are assigned to manage individual air missions. They tend to be overburdened with associated data monitoring and constraint checking, and generally react to detected problems in a local, myopic fashion. Consequently, decisions taken for one mission can often have deleterious effects on others. FMA combines two key capabilities for overcoming these problems: (1) intelligent monitoring of incoming information (for example, weather, airport operations, aircraft status) and recognizing those situations that require corrective action, and (2) dynamic rescheduling of missions in response to detected problems, both to understand the global implications of changed circumstances and to determine appropriate rescheduling actions. FMA builds on two of our existing technologies: an execution-monitoring framework previously applied to small-unit operations and control of robots, and a dynamic scheduling tool that is transitioning into operational use in AMC's Tanker/Airlift Control Center. FMA's dynamic mediation module provides for collaborative mission management by different planning and execution offices by structuring communication for decision making.

David E. Wilkins and Thomas J. Lee and Pauline Berry,
"Interactive Execution Monitoring of Agent Teams" (PDF),
Journal of Artificial Intelligence Research, volume 18, pages 217-261, March 2003

Abstract: There is an increasing need for automated support for humans monitoring the activity of distributed teams of cooperating agents, both human and machine. We characterize the domain-independent challenges posed by this problem, and describe how properties of domains influence the challenges and their solutions. We will concentrate on dynamic, data-rich domains where humans are ultimately responsible for team behavior. Thus, the automated aid should interactively support effective and timely decision making by the human. We present a domain-independent categorization of the types of alerts a plan-based monitoring system might issue to a user.

We use this framework to describe an execution monitoring approach we have used to implement Execution Assistants (EAs) in two different dynamic, data-rich, real-world domains to assist a human in monitoring team behavior. One domain (Army small unit operations) has hundreds of mobile, geographically distributed agents, a combination of humans, robots, and vehicles. The other domain (teams of unmanned ground and air vehicles) has a handful of cooperating robots. Both domains involve unpredictable adversaries in the vicinity. Our approach customizes monitoring behavior for each specific task, plan, and situation, as well as for user preferences. Our EAs alert the human controller when reported events threaten plan execution or physically threaten team members. Alerts were generated in a timely manner without inundating the user with too many alerts.

Vincent, R. and Berry, P. and Agno, A. and Ortiz, C. and Wilkins, D.
Teambotica: a robotic framework for integrated teaming, tasking, networking, and control, in Autonomous Agents and Multiagent Systems Conference, 2003.

D. E. Wilkins and M. desJardins,
A Call for Knowledge-based Planning, AI Magazine, Spring 2001, volume 22, number 1, pages 99-115.
A preliminary shorter version appeared in the 2nd International NASA Workshop on Planning and Scheduling for Space, March 16th to 18th 2000, San Francisco, CA, pages 187-192.

Abstract: We are interested in solving real-world planning problems and, to that end, argue for the use of domain knowledge in planning. We believe that the field must develop methods capable of using rich knowledge models in order to make planning tools useful for complex problems. We discuss the suitability of current planning paradigms for solving these problems. In particular, we compare knowledge-rich approaches such as hierarchical task network (HTN) planning to minimal-knowledge methods such as STRIPS-based planners and disjunctive planners (DPs). We argue that the former methods have advantages such as scalability, expressiveness, continuous plan modification during execution, and the ability to interact with humans. However, these planners also have limitations, such as requiring complete domain models and failing to model uncertainty, that often make them inadequate for real-world problems.

In this paper, we define the terms knowledge-based (KB) and primitive-action (PA) planning, and argue for the use of KB planning as a paradigm for solving real-world problems. We next summarize some of the characteristics of real-world problems that we are interested in addressing. Several current real-world planning applications are described, focusing on the ways in which knowledge is brought to bear on the planning problem. We describe some existing KB approaches, and then discuss additional capabilities, beyond those available in existing systems, that are needed. Finally, we draw an analogy from the current focus of the planning community on disjunctive planners to the experiences of the machine learning community over the past decade.

Working documents on MPA:

D. E. Wilkins and K. L. Myers,
"A Multiagent Planning Architecture," (PDF), available as a postcript file,
Proceedings of AIPS-98, pp. 154--162, June 1998.

Abstract: The Multiagent Planning Architecture (MPA) is a framework for integrating diverse technologies into a system capable of solving complex planning problems. Agents within MPA share well-defined, uniform interface specifications that facilitate integration of new technologies and experimentation with different problem-solving strategies. MPA provides a central repository for storing plan-related information in a shared plan representation, and metalevel agents that control and customize the interactions between other agents. The MPA framework has been validated through its use in developing several large-scale problem-solving systems for Air Campaign Planning.

D. E. Wilkins,
Using the SIPE-2 Planning System: A Manual for Version 6.1, (about 230 pages, PDF, 1.1MB)
available as a postcript file, 5MB,
available as a DVI file, 0.7MB,
SRI International Artificial Intelligence Center, Menlo Park, CA, July 1999.

Abstract: This document is intended to help new users of SIPE-2 get started. Readers wishing to program in SIPE-2 should be familiar with the representational ideas underlying the system which can be found in the book Practical Planning: Extending the Classical AI Planning Paradigm, by D. E. Wilkins, Morgan Kaufmann Publishers Inc., 1988, and in the sections of this document denoted as advanced concepts. This document should not be treated as a polished or comprehensive reference. It will not be complete or even correct, as the SIPE-2 system is constantly changing.

K. L. Myers and D. E. Wilkins,
"The Act Formalism", Version 2.2, (pdf),
SRI International Artificial Intelligence Center, Menlo Park, CA, September 1997.

Abstract: Provides a brief overview of the Act formalism, including a BNF grammar specification of Act.

K. L. Myers and D. E. Wilkins,
The Act-Editor User's Guide: A Manual for Version 2.2, (pdf)
, SRI International Artificial Intelligence Center, Menlo Park, CA, September 1997.

Abstract: The Act Formalism provides a medium in which to express knowledge about actions for both the SIPE-2 plan generation system and the PRS plan execution system. This document describes the Act-Editor, which provides a graphical user interface for creating and manipulating Acts. The document is designed for individuals who are already familiar with the Act formalism. The Act-Editor runs on Sun workstations and Windows with Allegro Common Lisp and on Macintoshes with MCL.

K. L. Myers and D. E. Wilkins,
"Reasoning about Locations in Theory and Practice," (PDF), available as a postcript file,
Computational Intelligence Journal, volume 14(2), pp. 151--187, 1998.

Abstract: Locational reasoning plays an important role in many applications of AI problem-solving systems, yet has remained a relatively unexplored area of research. This paper addresses both theoretical and practical issues relevant to reasoning about locations. We define several theories of location designed for use in various settings, along with a sound and complete belief revision calculus for each that maintains a STRIPS-style database of locational facts. Techniques for the efficient operationalization of the belief revision rules in planning frameworks are presented. These techniques were developed during application of the location theories to several large-scale planning tasks within the SIPE-2 planning framework.

P. D. Karp, K. L. Myers, D. E. Wilkins, and J. D. Lowrance
"AIC Software Specifications" (postscript),
SRI International Artificial Intelligence Center, Menlo Park, CA, Version 5.4, April 1997.

Abstract: This document lays out a set of conventions for managing the major software systems in use at the Artificial Intelligence Center (AIC), and documents software written to support these conventions. One reason for needing such conventions is that many of these software systems are used by a number of different people. People may wish to simply run the system, or to use the system as a foundation for building another system, or to recompile the system. Until now, every system has required the user to employ a completely different procedure for performing these tasks, leading to great confusion. Other important features provided by the AIC system software include version control and a patch facility.

This document defines a uniform set of Lisp functions, Unix shell commands, and Unix Make operations that should be implemented for every AIC software system. The conventions pertain to system directory structures, and operations for loading, compiling, running, and distributing (to sites outside SRI) the system.

D. E. Wilkins,
"That's something I cannot allow to happen: HAL and Planning," in HAL's Legacy: 2001's Computer as Dream and Reality,
edited by David G. Stork, foreword by Arthur C. Clarke, MIT Press, 1997.

"David E. Wilkins' comments on HAL's bad planning but impressive improvisation ..... makes for delightful reading"
---- Paul Preuss, San Jose Mercury News Book Reviews, 12 January 1997.

Thomas J. Lee and David E. Wilkins,
"Using SIPE-2 to integrate planning for military air campaigns,"
IEEE Expert 11(6), December 1996, pp. 11-12.

John Mark Agosta and David E. Wilkins,
"Using SIPE-2 to plan emergency response to marine oil spills," (expanded version) IEEE Expert 11(6), December 1996, pp. 6-8.

D. E. Wilkins, K. L. Myers, J. D. Lowrance, and L. P. Wesley,
"Planning and reacting in uncertain and dynamic environments," (PDF) available as a postcript file,
Journal of Experimental and Theoretical AI, vol. 7, no. 1, pp. 197-227, 1995.

Abstract: Agents situated in dynamic and uncertain environments require several capabilities for successful operation. Such agents must monitor the world and respond appropriately to important events. The agents should be able to accept goals, synthesize complex plans for achieving those goals, and execute the plans while continuing to be responsive to changes in the world. As events render some current activities obsolete, the agents should be able to modify their plans while continuing activities unaffected by those events. The Cypress system is a domain-independent framework for defining persistent agents with this full range of behavior. Cypress has been used for several demanding applications, including military operations, real-time tracking, and fault diagnosis.

D. E. Wilkins and K. L. Myers,
"A common knowledge representation for plan generation and reactive execution," (PDF), available as a postcript file,
Journal of Logic and Computation, vol. 5, number 6, pp. 731--761, December 1995.

Abstract: The ability to integrate sophisticated planning techniques with reactive execution systems is critical for nontrivial applications. Merging these two technologies is difficult because the forms of knowledge and reasoning that they employ differ substantially. The ACT formalism is a language for representing the knowledge required to support both the generation of complex plans and reactive execution of those plans in dynamic environments. A design goal of ACT was its adequacy for practical applications. ACT has been used as the interlingua in an implemented system that links a previously implemented planner with a previously implemented executor. This system has been used in several applications, including robot control and military operations, thus attesting to its expressive and computational adequacy.

D. E. Wilkins and R. V. Desimone,
"Applying an AI planner to military operations planning," (postscript), PDF version,
in Intelligent Scheduling (M. Fox and M. Zweben, eds.), pp. 685--709, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994.

Abstract: This paper describes a prototype system for quickly developing joint military courses of action. The system, SOCAP (System for Operations Crisis Action Planning), combines a newly extended version of an AI planning system, SIPE-2 (System for Interactive Planning and Execution), with a color map display and applies this technology to military operations planning. This paper describes the Socap problem domain, how SIPE-2 was used to address this problem, and the strengths and weaknesses of our approach.

D. E. Wilkins,
Using the SIPE-2 Planning System: A Manual for Version 4.9,
SRI International Artificial Intelligence Center, Menlo Park, CA, July 1995.

D. E. Wilkins and K. L. Myers,
"Integrating planning and reactive control," (postscript)
in Third International Symposium on Artificial Intelligence, Robotics, and Automation for Space, (Jet Propulsion Laboratory, Pasadena, CA), 1994.

D. E. Wilkins, K. L. Myers, and L. P. Wesley,
"Cypress: planning and reacting under uncertainity,"
in ARPA/Rome Laboratory Planning and Scheduling Initiative Workshop Proceedings (M. H. Burstein, ed.), pp. 111--120, Morgan Kaufmann Publishers Inc., San Francisco, CA, Feb. 1994.

P. D. Karp, J. D. Lowrance, T. M. Strat, and D. E. Wilkins,
"The Grasper-CL graph management system," (compressed postscript)
LISP and Symbolic Computation, vol. 7, pp. 245--282, 1994.

Abstract: Grasper-CL is a system for manipulating and displaying graphs, and for building graph-based user interfaces for application programs. It is implemented in Common Lisp and CLIM, and has been proven by use in a number of applications. Grasper-CL includes several advances in graph drawing. It contains a graph abstract datatype plus a comprehensive and novel language of operations on that datatype. The appearance of Grasper-CL can be tailored by a wide variety of shape parameters that allow the application to customize the display of nodes and edges for different domains. Default values for shape parameters can be established at several levels. Grasper-CL a toolbox approach to graph layout: the system contains a suite of graph layout algorithms that can be applied individually, or in combination to produce hierarchical graph layouts. The system also contains an interactive graph browser.

J. D. Lowrance and D. E. Wilkins,
"Plan evaluation under uncertainity," (postscript)
in Proceedings of the Workshop on Innovative Approaches to Planning, Scheduling and Control (K. P. Sycara, ed.), pp. 439--449, Morgan Kaufmann Publishers Inc., San Francisco, CA, Nov. 1990.

D. E. Wilkins,
"Can AI planners solve practical problems?," (PDF), available as a postcript file,
Computational Intelligence, vol. 6, no. 4, pp. 232--246, 1990.

Abstract: While there has been recent interest in research on planning and reasoning about actions, nearly all research results have been theoretical. We know of no previous examples of a planning system that has made a significant impact on a problem of practical importance. One of the primary goals during the development of the SIPE-2 planning system has been the balancing of efficiency with expressiveness and flexibility. With a major new extension, SIPE-2 has begun to address practical problems. This paper describes this new extension and the new applications of the planner. One of these applications is the problem of producing products from raw materials on process lines under production and resource constraints. This is a problem of commercial importance and SIPE-2's application to it is described in some detail.

D. E. Wilkins,
Practical Planning: Extending the Classical AI Planning Paradigm.
Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988.

D. E. Wilkins,
"Causal reasoning in planning,"
Computational Intelligence, vol. 4, no. 4, pp. 373--380, 1988.

Abstract: Reasoning about actions necessarily involves tracking the truth of assertions about the world over time. The SIPE planning system retains the efficiency of the STRIPS assumption for this while enhancing expressive power by allowing the specification of a causal theory. Separation of knowledge about causality from knowledge about actions relieves operators of much of their representational burden and allows them to be applicable in a wide range of contexts. The implementation of causal theories is described, together with examples and evaluations of the system's expressive power and efficiency.

D. E. Wilkins,
"Hierarchical planning: Definition and implementation,"
in Advances in Artificial Intelligence II (Boulay, Hogg, and Steels, eds.), pp. 659--671, North-Holland, 1987.

Abstract: There is considerable ambiguity involved in hierarchical planning. We present a definition of the latter, and examine several of the reasons for this confusion. An explication of hierarchical-planning implementations entails two distinct notions: abstraction level and planning level. A problem in currently implemented planners that is caused by mixing these two levels is presented and various remedies suggested. Three solutions that have been implemented in the current SIPE planning system are described.

D. E. Wilkins,
"High-level planning in a mobile robot domain,"
Technical Report 388, SRI International Artificial Intelligence Center, Menlo Park, CA, July 1986.

D. E. Wilkins,
"Recovering from execution erors in SIPE,"
Computational Intelligence, vol. 1, no. 1, pp. 33--45, 1985.

Abstract: In real-world domains (e.g., a mobile robot environment), things do not always proceed as planned, so it is important to develop better execution-monitoring techniques and replanning capabilities. This paper describes these capabilities in the SIPE planning system. The motivation behind SIPE is to place enough limitations on the representation so that planning can be done efficiently, while retaining sufficient power to still be useful. This work assumes that new information given to the execution monitor is in the form of predicates, thus avoiding the difficult problem of how to generate these predicates from information provided by sensors. The replanning module presented here takes advantage of the rich structure of SIPE plans and is intimately connected with the planner, which can be called as a subroutine. This allows the use of SIPE's capabilities to determine efficiently how unexpected events affect the plan being executed and, in many cases, to retain most of the original plan by making changes in it to avoid problems caused by these unexpected events. SIPE is also capable of shortening the original plan when serendipitous events occur. A general set of replanning actions is presented along with a general replanning capability that has been implemented by using these actions.

D. E. Wilkins,
"Domain-independent planning: Representation and plan generation,"
Artificial Intelligence, vol. 22, no. 3, pp. 269--301, 1984.

Abstract: A domain-independent planning program that supports both automatic and interactive generation of hierarchical, partially ordered plans is described. An improved formalism makes extensive use of constraints and resources to represent domains and actions more powerfully. The formalism also offers efficient methods for representing properties of objects that do not change over time, allows specification of the plan rationale (which includes scoping of conditions and appropriately relating different levels in the hierarchy), and provides the ability to express deductive rules for deducing the effects of actions. The implications of allowing parallel actions in a plan or problem solution are discussed, and new techniques for efficiently detecting and remedying harmful parallel interactions are presented. The most important of these techniques, reasoning about resources, is emphasized and explained. The system supports concurrent exploration of different branches in the search, making best-first search easy to implement.

D. E. Wilkins, "Using chess knowledge to reduce search," in Chess Skill in Man and Machine (P. Frey, ed.), ch. 10, Springer-Verlag, 1983.

Abstract: The current generation of computer chess programs select a move by exploring huge lookahead trees (millions of positions). Human masters, on the other hand, appear to use a knowledge-intensive approach to chess. They seem to have a huge number of stored ``patterns", and analyzing a position involves matching these patterns to suggest plans for attack or defense. This analysis is verified and possibly corrected by a small search of the game tree (tens of positions). This chapter describes a program named PARADISE (PAttern Recognition Applied to DIrecting SEarch) which uses this approach in an attempt to find the best move in tactically sharp middle game positions from the games of chess masters.

In Chapter 4 the authors of the Northwestern University chess program state that their program is ``devoid of chess knowledge" not because they have deliberately traded it for speed of execution, but because ``the programming tools we are presently using are not adequate to the task". PARADISE was developed to investigate the issues involved in expressing and using pattern-oriented knowledge to analyze a chess position, to provide direction for the search, and to communicate useful results from the search.

PARADISE encodes a large body of chess knowledge, which is used to match patterns in the chess position and post concepts in the data base. The program uses the knowledge base to discover plans during static analysis of a position and to guide a small tree search that confirms that a particular plan is best. The search is ``small" in the sense that the size of the search tree is of the same order of magnitude as a human master's search tree. Because it grows small trees, PARADISE can find deeper combinations than most chess programs.

D. E. Wilkins, "Using knowledge to control tree searching," Artifical Intelligence, vol. 18, pp. 1--51, 1982.

D. E. Wilkins, "Using patterns and plans in chess," in Readings in Artificial Intelligence (B. Weber and N. Nilsson, eds.), pp. 390--409, Tioga Publishing, 1981.

D. E. Wilkins, "Using patterns and plans in chess," Artifical Intelligence, vol. 14, pp. 165--203, 1980.

Earlier papers.

Back to Wilkins Home Page (additional bibliography entries)

David E. Wilkins
Last modified: Mon Sep 12 16:32:28 PDT 2005