Papers by David E. Wilkins

Hasnain Lakhani, Tim McCarthy, Minyoung Kim, David E. Wilkins, and Samuel Wood, Evaluation of a Delay-Tolerant ICN Architecture. In Proceedings of the seventh International Conference on Ubiquitous and Future Networks (ICUFN 2015), Excellent Paper Award, Sapporo, Japan. July, 2015.

Abstract: Simulation/emulation is key for early testing, assessment, and scalability evaluation of networking solutions for mobile ad-hoc networks (MANETs). If the solution is highly configurable -- such as ENCODERS, SRI's delay-tolerant information-centric networking (ICN) solution -- this type of evaluation is crucial. For effective modeling of information flows, the test framework needs to: (1) allow repeatable execution of scenarios with different patterns of network traffic, operating in different mobility and network-usage contexts, (2) provide a rich simulated environment that can model virtually any network topology and mobility, with high-fidelity device models, and (3) support flexible large-scale simulation, with the option of using virtual machines that execute the same code that would be used on an actual device. We describe our evaluation framework and the results of using it to develop and evaluate ENCODERS.

Terry Zimmerman, Laura Barbulescu, Zachary Rubinstein, Stephen Smith and David E. Wilkins, Distributed Scheduling Agents for Disaster Response. In Proceedings of the ICAPS 2010 Scheduling and Planning Applications woRKshop, Toronto, Canada, pp. 7-14. May 13, 2010.

Abstract: We describe the application of a multiagent framework for collaborative scheduling to a disaster-response coordination problem. The problem is a field-exercise mockup of a natural disaster, where a team of human agents must rely on their respective automated scheduling agents to coordinate and accomplish various infrastructure-repair and casualty-transport tasks. We developed a collaborative scheduling framework under the strong assumption that no single agent has a global view of the overall problem. This peer-to-peer approach to multigent scheduling and coordination gives rise to a complex distributed search problem, and effective performance in the field exercise was found to depend heavily on the ability to provide the multiagent system with strong initial strategic guidance. We describe the mechanisms developed for steering the multiagent scheduling system to address specific disaster-response scenarios and report performance results that were obtained in the field exercise.

Denker, G. and Elenius, D. and Wilkins D. Cognitive Radio Policy Language and Policy Engine. Cognitive Radio Technology, Second Edition, Bruce Fette ed., Elsevier, pp. 557-592, ISBN: 9780123745354, 2009.

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

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 recognition of 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.

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, DOI: 10.1109/MWC.2007.4300982, 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, Mark-Oliver Stehr, Rukman Senanayake, Daniel Elenius, Carolyn L. Talcott, and David Wilkins,
"CoRaL - Policy Language and Reasoning Techniques for Spectrum Policies", 8th IEEE International Symposium on Policies for Distributed Systems and Networks (POLICY 2007), Bologna, Italy, 13-15 June 2007.

Abstract: We present the Cognitive Radio (Policy) Language (CoRaL), a new language for expressing policies that govern the behavior of cognitive radios that opportunistically share spectrum. A Policy Reasoner validates radio transmissions to ensure that they are compliant with the spectrum policies. The Policy Reasoner also discovers spectrum sharing opportunities by deriving what requirements have to be fulfilled for transmissions to be valid, i.e., in compliance with policies. A novel mix of reasoning techniques is required to implement such a reasoner. We will give an overview of our approach and explain how it is related to traditional research in logic programming and automated reasoning.

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.
2.5 minute video by Grit Denker.

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, 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. 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.

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.
JAIR versions of the paper, HTML version of the paper.

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 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.

2 papers on SIPE-2 by others:

Marie desJardins and Michael Wolverton.
"Coordinating a distributed planning system." In AI Magazine, 20(4): 45-53, Winter 1999.

Marie desJardins and Michael Wolverton. "Controlling communication in distributed planning using irrelevance reasoning." In Proceedings of the Fifteenth National Conference on Artificial Intelligence, Madison, WI, AAAI Press, pp. 868-874, 1998.

David E. Wilkins, Karen L. Myers, Marie desJardins, Pauline M. Berry,
Multiagent Planning Architecture, summary, 1998, around 36 pages, a subset of the above, without documentation for MPA wrapper functions and without precise agent interface specifications.

D. E. Wilkins and K. L. Myers,
"A Multiagent Planning Architecture",
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)
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,
"Reasoning about Locations in Theory and Practice," (PDF),
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.

Drew Mcdermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins
"PDDL - The Planning Domain Definition Language",
Technical report, CVC TR-98-003/DCS TR-1165, Yale Center for Computational Vision and Control, 1998.

Abstract: This manual describes the syntax of PDDL, the Planning Domain Definition Language, the problem-specification language for the AIPS-98 planning competition. The language has roughly the the expressiveness of Pednault's ADL for propositions, and roughly the expressiveness of UMCP for actions. Our hope is to encourage empirical evaluation of planner performance, and development of standard sets of problems all in comparable notations.

K. L. Myers and D. E. Wilkins,
The Act Formalism, Version 2.2,
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 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.

D. E. Wilkins, "That's something I cannot allow to happen: HAL and Planning,", by David E. Wilkins in HAL's Legacy: 2001's Computer as Dream and Reality, edited by David G. Stork, foreword by Arthur C. Clarke, MIT Press, ISBN: 0262193787, paperback: 9780262692113, 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.

P. D. Karp, K. L. Myers, D. E. Wilkins, and J. D. Lowrance
"AIC Software Specifications" ,
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. These conventions support loading, compiling, running, and distributing (to sites outside SRI) the system, using the system as a module in another system, building an image, patching the system, and version control. 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.

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", 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.

M. Bienkowski and M. desJardins and R. Desimone.
"SOCAP: system for operations crisis action planning",
Proc. of the ARPA/Rome Lab 1994 Knowledge-Based Planning and Scheduling Initiative Workshop, pp. 219-228, Morgan Kaufmann Publishing, 1994.

Abstract: We report on our past and recent experiences in applying an AI generative planning system, called System for Interactive Planning and Execution (SIPE-2), to the problem of generating crisis action operations plans in a joint military domain. We report on the applied research we performed to address the lessons learned. This involved integrating the generative planner with several complementary technologies: a temporal reasoner, a case-based reasoner, and the capacity analysis component of a scheduling system. Section 4 describes temporal reasoning and scheduling in SIPE-2. http://citeseer.ist.psu.edu/bienkowski94socap.html

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,"
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," 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.

Roberto Desimone, David E. Wilkins, Marie Bienkowski, and Marie desJardins.
SOCAP: Lessons learned in automating military operations planning. Proc. of the Sixth International Conference on Industrial and Engineering Applications of AI and Expert Systems, Edinburgh, Scotland, June, 1993.

J. D. Lowrance and D. E. Wilkins, "Plan evaluation under uncertainity,"
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?,"
Computational Intelligence, DOI: 10.1111/j.1467-8640.1990.tb00297.x, 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. This book helped define hierarchical planning techniques in AI.

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, DOI: 10.1111/j.1467-8640.1985.tb00057.x, vol. 1, no. 1, pp. 33--45, January 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, April 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. 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, doi:10.1016/0004-3702(82)90009-1, vol. 18, Issue 1, pp. 1--51, January 1982.

Abstract: PARADISE (PAttern Recognition Applied to DIrecting SEarch) uses a knowledge-based analysis and little searching to find the correct move in chess middle game positions. PARADISE's search does not have a depth limit or any other artificial effort limit. This paper describes the methods used to constrain the search. The ideas of using different strategies to show that one move is best and using ranges to express the values of moves (first developed in Berliner's B* search), are extended and clarified. PARADISE combines these ideas with the use of plans, a threshold, and various measures of possibility. Examples are presented, including one in which PARADISE uses an indirect strategy to prove that one move is best without finding the winning line (a first for a chess program).

D. E. Wilkins, Using patterns and plans in chess,
Artifical Intelligence, doi:10.1016/0004-3702(80)90039-9, vol. 14, Issue 2, pp. 165--203, Sept, 1980.

also in Readings in Artificial Intelligence (B. Weber and N. Nilsson, eds.), pp. 390--409, Tioga Publishing, 1981.

Abstract The purpose of this research is to investigate the extent to which knowledge can replace and support search in selecting a chess move and to delineate the issues involved. This has been carried out by constructing a program, PARADISE (PAttern Recognition Applied to DIrecting SEarch), which finds the best move in tactically sharp middle game positions from the games of chess masters. It encodes a large body of knowledge in the form of production rules. The actions of the rules post concepts in the data base while the conditions match patterns in the chess position and data base. The program uses the knowledge base to discover plans during static analysis and to guide a small tree search which 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 (tens and hundreds of nodes, not thousands to hundreds of thousands as in many computer chess programs). Once a plan is formulated, it guides the tree search for several ply and expensive static analyses (needed to analyze a new position) are done infrequently. PARADISE avoids placing a depth limit on the search (or any other artificial effort limit). By using a global view of the search tree, information gathered during the search, and the analysis provided by the knowledge base, the program produces enough terminations to force convergence of the search. PARADISE has found combinations as deep as 19 ply.

D. E. Wilkins, "Causality analysis in chess," in CSCSI Proceedings, (Victoria, BC), 1980.

D. E. Wilkins, "Using plans in chess," in Proceedings of the 1979 International Joint Conference on Artificial Intelligence, (Tokyo, Japan), pp. 960--967, 1979.

D. E. Wilkins, "Using Patterns and Plans to Solve Problems and Control Search," Ph.D. thesis, Computer Science Dept, Stanford University, Stanford, California, AI Lab Memo AIM-329, 1979.

Papers on chess, 1979-1991.

D. E. Wilkins, A non-clausal theorem proving system,
in Proceeedings of 1974 AISB Conference (Society for the Study of Artificial Intelligence and Simulation of Behaviour), Sussex, UK, pp. 257--267, 1974.

Abstract: There are reasons to suspect that non-clausal first-order logic expressions will provide a better base for a theorem prover than conventional clausal form. A complete inference system, QUEST, for the first-order predicate calculus using expressions in prenex form is presented. Comparison of this system with SL-resolution shows that clausal techniques can be transferred to prenex form and expected advantages do seem to appear.

pdf file from Proc. 1974 AISB Conference proceedings. Papers by P. Hayes, D. Michie, D. Luckham, A. Mackworth, A. Sloman, C. Hewitt, Jay Sussman, Y. Wilks,... from http://homepages.inf.ed.ac.uk/bundy/publications.html

Wilkins Home Page (additional bibliography entries)