CiteULike: cyph3r's library [139 articles]

The chaining approach for software test data generation

Roger Ferguson — 2006-06-23T15:16:31-00:00

ACM Trans. Softw. Eng. Methodol., Vol. 5, No. 1. (January 1996), pp. 63-86.

Feedback-Directed Random Test Generation

Carlos Pacheco — 2007-10-09T15:01:20-00:00

(2007), pp. 75-84.

EXE: automatically generating inputs of death

Cristian Cadar — 2007-07-06T07:14:41-00:00

(2006), pp. 322-335.

Generating test data from state-based specifications

Jeff Offutt — 2008-08-06T16:43:43-00:00

Software Testing, Verification and Reliability, Vol. 13, No. 1. (2003), pp. 25-53.

Although the majority of software testing in industry is conducted at the system level, most formal research has focused on the unit level. As a result, most system-level testing techniques are only described informally. This paper presents formal testing criteria for system level testing that are based on formal specifications of the software. Software testing can only be formalized and quantified when a solid basis for test generation can be defined. Formal specifications represent a significant opportunity for testing because they precisely describe what functions the software is supposed to provide in a form that can be automatically manipulated.This paper presents general criteria for generating test inputs from state-based specifications. The criteria include techniques for generating tests at several levels of abstraction for specifications (transition predicates, transitions, pairs of transitions and sequences of transitions). These techniques provide coverage criteria that are based on the specifications and are made up of several parts, including test prefixes that contain inputs necessary to put the software into the appropriate state for the test values. The test generation process includes several steps for transforming specifications to tests. These criteria have been applied to a case study to compare their ability to detect seeded faults. Copyright © 2003 John Wiley & Sons, Ltd.

Generating software test data by evolution

CC Michael — 2008-05-16T08:03:23-00:00

Software Engineering, IEEE Transactions on, Vol. 27, No. 12. (2001), pp. 1085-1110.

This paper discusses the use of genetic algorithms (GAs) for automatic software test data generation. This research extends previous work on dynamic test data generation where the problem of test data generation is reduced to one of minimizing a function. In our work, the function is minimized by using one of two genetic algorithms in place of the local minimization techniques used in earlier research. We describe the implementation of our GA-based system and examine the effectiveness of this approach on a number of programs, one of which is significantly larger than those for which results have previously been reported in the literature. We also examine the effect of program complexity on the test data generation problem by executing our system on a number of synthetic programs that have varying complexities

On path-wise automatic generation of test data for both white-box and black-box testing

Jin-Hui Shan — 2008-08-06T16:40:19-00:00

Software Engineering Conference, 2001. APSEC 2001. Eighth Asia-Pacific (2001), pp. 237-240.

Automatic generation of test data for a given path in a program is an elementary problem in software testing, the difficulty of which lies in how to solve the nonlinear constraint. Gupta et al. (1998) proposed a method, which is referred to as the iterative relaxation method, to address the above problem by linearizing the predicate functions. This paper improves the iterative relaxation method by omitting the constructions of predicate slice and input dependency set, and proves the equivalence of systems of constraints generated by both methods. Since it is not necessary for our method to analyze the dependencies between statements on the path in the course of deriving a system of constraints, our method still works when some statements are only object or executable codes rather than source codes on the path. Therefore, our method can also be used for generating test data for black-box testing and regression testing. We have developed a prototype of a path-wise test data generator whose fundamental algorithm is presented in this paper. The initial experiments with this prototype have shown that our method is practical.

Automatic test data generation using genetic algorithm and program dependence graphs

James Miller — 2008-08-06T16:39:14-00:00

Information and Software Technology, Vol. 48, No. 7. (July 2006), pp. 586-605.

The complexity of software systems has been increasing dramatically in the past decade, and software testing as a labor-intensive component is becoming more and more expensive. Testing costs often account for up to 50% of the total expense of software development; hence any techniques leading to the automatic generation of test data will have great potential to considerably reduce costs. Existing approaches of automatic test data generation have achieved some success by using evolutionary computation algorithms, but they are unable to deal with Boolean variables or enumerated types and they need to be improved in many other aspects. This paper presents a new approach utilizing program dependence analysis techniques and genetic algorithms (GAs) to generate test data. A set of experiments using the new approach is reported to show its effectiveness and efficiency based upon established criterion.

Eclat: Automatic Generation and Classification of Test Inputs

Carlos Pacheco — 2007-10-18T18:23:30-00:00

ECOOP 2005 - Object-Oriented Programming (2005), pp. 504-527.

This paper describes a technique that selects, from a large set of test inputs, a small subset likely to reveal faults in the software under test. The technique takes a program or software component, plus a set of correct executions — say, from observations of the software running properly, or from an existing test suite that a user wishes to enhance. The technique first infers an operational model of the software’s operation. Then, inputs whose operational pattern of execution differs from the model in specific ways are suggestive of faults. These inputs are further reduced by selecting only one input per operational pattern. The result is a small portion of the original inputs, deemed by the technique as most likely to reveal faults. Thus, the technique can also be seen as an error-detection technique. The paper describes two additional techniques that complement test input selection. One is a technique for automatically producing an oracle (a set of assertions) for a test input from the operational model, thus transforming the test input into a test case. The other is a classification-guided test input generation technique that also makes use of operational models and patterns. When generating inputs, it filters out code sequences that are unlikely to contribute to legal inputs, improving the efficiency of its search for fault-revealing inputs. We have implemented these techniques in the Eclat tool, which generates unit tests for Java classes. Eclat’s input is a set of classes to test and an example program execution—say, a passing test suite. Eclat’s output is a set of JUnit test cases, each containing a potentially fault-revealing input and a set of assertions at least one of which fails. In our experiments, Eclat successfully generated inputs that exposed fault-revealing behavior; we have used Eclat to reveal real errors in programs. The inputs it selects as fault-revealing are an order of magnitude as likely to reveal a fault as all generated inputs.

Experiments with Test Case Generation and Runtime Analysis

Cyrille Artho — 2007-06-19T06:58:09-00:00

Abstract State Machines 2003. Advances in Theory and Practice: 10th International Workshop, ASM 2003, Taormina, Italy, March 3-7, 2003. Proceedings (2003), 87.

Software testing is typically an ad hoc process where human testers manually write many test inputs and expected test results, perhaps automating their execution in a regression suite. This process is cumbersome and costly. This paper reports preliminary results on an approach to further automate this process. The approach consists of combining automated test case generation based on systematically exploring the program's input domain, with runtime analysis, where execution traces are monitored and verified against temporal logic specifications, or analyzed using advanced algorithms for detecting concurrency errors such as data races and deadlocks. The approach suggests to generate specifications dynamically per input instance rather than statically once-and-for-all. The paper describes experiments with variants of this approach in the context of two examples, a planetary rover controller and a space craft fault protection system.

Automated Test Data Generation Using an Iterative Relaxation Method

Neelam Gupta — 2008-08-05T11:10:08-00:00

(1998), pp. 231-244.

An important problem that arises in path oriented testing is the generation of test data that causes a program to follow a given path. In this paper, we present a novel program execution based approach using an iterative relaxation method to address the above problem. In this method, test data generation is initiated with an arbitrarily chosen input from a given domain. This input is then iteratively refined to obtain an input on which all the branch predicates on the given path evaluate to the ...

Understanding and Extending Graphplan

Subbarao Kambhampati — 2008-08-05T11:07:20-00:00

(1997), pp. 260-272.

We provide a reconstruction of Blum and Furst's Graphplan algorithm, and use the reconstruction to extend and improve the original algorithm in several ways. In our reconstruction, the process of growing the planning-graph and inferring mutex relations corr esponds to doing forward state-space refinement over disjunctively represented plans. The backward search phase of Graphplan corresponds to solving a binary dynamic constraint satisfaction problem. Our reconstruction sheds light on the...

Mining object behavior with ADABU

Valentin Dallmeier — 2008-05-23T07:25:08-00:00

(2006), pp. 17-24.

Automatic extraction of abstract-object-state machines from unit-test executions

Tao Xie — 2008-07-18T12:00:23-00:00

(2006), pp. 835-838.

Toward a theory of test data selection

John Goodenough — 2007-06-06T11:54:36-00:00

(1975), pp. 493-510.

Automated testing in software engineering: using ant colony and self-regulated swarms

PK Mahanti — 2008-08-02T10:19:17-00:00

(2006), pp. 443-448.

Application of AI Planning Techniques to Automated Code Synthesis and Testing

I-Ling Yen — 2008-08-02T10:13:21-00:00

(2002)

Planner Based Error Recovery Testing

Anneliese von Mayrhauser — 2008-08-02T10:12:03-00:00

(2000)

Rapid goal-oriented automated software testing using MEA-graph planning

Manish Gupta — 2008-01-10T11:53:09-00:00

Software Quality Journal, Vol. 15, No. 3. (2007), pp. 241-263.

Abstract With the rapid growth in the development of sophisticated modern software applications, the complexity of the software development process has increased enormously, posing an urgent need for the automation of some of the more time-consuming aspects of the development process. One of the key stages in the software development process is system testing. In this paper, we evaluate the potential application of AI planning techniques in automated software testing. The key contributions of this paper include the following: (1) A formal model of software systems from the perspective of software testing that is applicable to important classes of systems and is amenable to automation using AI planning methods. (2) The design of a framework for an automated planning system (APS) for applying AI planning techniques for testing software systems. (3) Assessment of the test automation framework and a specific AI Planning algorithm, namely, MEA-Graphplan (Means-Ends Analysis Graphplan), algorithm to automatically generate test data. (4) A case study is presented to evaluate the proposed automated testing method and compare the performance of MEA-Graphplan with that of Graphplan. The empirical results show that for software testing, the MEA-Graphplan algorithm can perform computationally more efficiently and effectively than the basic Graph Planning algorithm.

"MeshUp": Self-organizing mesh-based topologies for next generation radio access networks

Samik Ghosh — 2006-12-26T11:23:54-00:00

Ad Hoc Networks, Vol. In Press, Uncorrected Proof

The phenomenal growth in wireless technologies has brought about a slew of new services. Incumbent with the new technology is the challenge of providing flexible, reconfigurable, self-organizing architectures which are capable of catering to the dynamics of the network, while providing cost-effective solutions for the service providers. In this paper, we focus on mesh-based multi-hop access network architectures for next generation radio access networks. Using short, high bandwidth optical wireless links to interconnect the various network elements, we propose a non-hierarchical, multi-hop access network framework. We study two generic family of mesh-based topologies: GPeterNet, a graph theoretic framework, and FraNtiC, a fractal geometric architecture, for arbitrary access network deployments. The performance of these topologies is analyzed in terms of different system metrics - topological robustness and reliability, system costs and network exposure due to failure conditions. Our analysis shows that a combination of different mesh-based multi-hop access topologies, coupled with emerging wireless backhaul technologies, can cater carrier-class services for next generation radio access networks, providing significant advantages over existing access technologies.

A resource-efficient and scalable wireless mesh routing protocol

Jianliang Zheng — 2006-12-26T08:06:05-00:00

Ad Hoc Networks, Vol. In Press, Uncorrected Proof

By binding logic addresses to the network topology, routing can be carried out without going through route discovery. This eliminates the initial route discovery latency, saves storage space otherwise needed for routing table, and reduces the communication overhead and energy consumption. In this paper, an adaptive block addressing (ABA) scheme is first introduced for logic address assignment as well as network auto-configuration purpose. The scheme takes into account the actual network topology and thus is fully topology-adaptive. Then a distributed link state (DLS) scheme is further proposed and put on top of the block addressing scheme to improve the quality of routes, in terms of hop count or other routing cost metrics used, robustness, and load balancing. The network topology reflected in logic addresses is used as a guideline to tell towards which direction (rather than next hop) a packet should be relayed. The next hop is derived from each relaying node's local link state table. The routing scheme, named as topology-guided DLS (TDLS) as a whole, scales well with regard to various performance metrics. The ability of TDLS to provide multiple paths also precludes the need for explicit route repair, which is the most complicated part in many wireless routing protocols. While this paper targets low rate wireless mesh personal area networks (LR-WMPANs), including wireless mesh sensor networks (WMSNs), the TDLS itself is a general scheme and can be applied to other non-mobile wireless mesh networks.

Developing a General Framework for Artificial Intelligence

Stephan Gspandl — 2008-07-28T11:14:32-00:00

3rd Austrian RoboCup Workshop (21 May 2008)

KickOffTUG - Team Description Paper 2008

Stephan Gspandl — 2008-07-28T11:01:52-00:00

(2008)

Data Generation for Path Testing

Nashat Mansour — 2008-07-24T09:22:38-00:00

Software Quality Journal, Vol. 12, No. 2. (1 June 2004), pp. 121-136.

We present two stochastic search algorithms for generating test cases that execute specified paths in a program. The two algorithms are: a simulated annealing algorithm (SA), and a genetic algorithm (GA). These algorithms are based on an optimization formulation of the path testing problem which include both integer- and real-value test cases. We empirically compare the SA and GA algorithms with each other and with a hill-climbing algorithm, Korel's algorithm (KA), for integer-value-input subject programs and compare SA and GA with each other on real-value subject programs. Our empirical work uses several subject programs with a number of paths. The results show that: (a) SA and GA are superior to KA in the number of executed paths, (b) SA tends to perform slightly better than GA in terms of the number of executed paths, and (c) GA is faster than SA; however, KA, when it succeeds in finding the solution, is the fastest.

Conformant Planning via Model Checking

Alessandro Cimatti — 2008-07-24T08:57:14-00:00

Recent Advances in AI Planning (2000), pp. 21-34.

Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal for any possible initial state and nondeterministic behavior of the planning domain. In this paper we present a new approach to conformant planning. We propose an algorithm that returns the set of all conformant plans of minimal length if the problem admits a solution, otherwise it returns with failure. Our work is based on the planning via model checking paradigm, and relies on symbolic techniques such as Binary Decision Diagrams to compactly represent and efficiently analyze the planning domain. The algorithm, called cmbp, has been implemented in the mbp planner. cmbp is strictly more expressive than the state of the art conformant planner sc cgp. Furthermore, an experimental evaluation suggests that cmbp is able to deal with uncertainties more efficiently than cgp.

Korat: automated testing based on Java predicates

Chandrasekhar Boyapati — 2005-11-26T09:03:53-00:00

Vol. 27, No. 4. (July 2002), pp. 123-133.

Encoding Plans in Propositional Logic

Henry Kautz — 2006-05-03T02:53:14-00:00

(1996), pp. 374-384.

In recent work we showed that planning problems can be efficiently solved by general propositional satisfiability algorithms (Kautz and Selman 1996). A key issue in this approach is the development of practical reductions of planning to SAT. We introduce a series of different SAT encodings for STRIPS-style planning, which are sound and complete representations of the original STRIPS specification, and relate our encodings to the Graphplan system of Blum and Furst (1995). We analyze...

An AI Planning Overview

Stefan Galler — 2008-07-22T09:43:11-00:00

(January 2006)

This paper presents an overview of AI planning approaches. Famous planners like STRIPS (Stanford Research Institute Problem Solver), Graphplan and SAT (Planning as Satisfiability) are considered. The international planning competition 2004 shows be- side that traditional planners heuristical search planners get more and more competitive. Because of the relevance of heuristical search planners the basic approach of them is ex- plained. Two selected representatives of this planners where considered in detail. The behavioral approach from Brooks for finding a solution to planning problems is considered too. This method does not use any search technique at all. It is based on the assumption that intelligence can be build up by combining unintelligent tasks. For a better understanding of different planners one example is used to explain selected planning processes. The example illustrates differences in the planning process very well. The paper takes into account prob- lems of STRIPS style planners too. Based on them possible extensions to these planners are considered. But finding a plan is not enough for real world problems. The plan must be executed to achieve the defined goal. Therefore plan execution is an important topic which is discussed at the end of the paper.

Software Test Data Generation using Ant Colony Optimization

Huaizhong — 2008-07-21T16:21:53-00:00

ROCEEDINGS OF WORLD ACADEMY OF SCIENCE, ENGINEERING AND TECHNOLOGY, No. 1. (January 2005), pp. 1-5.

A survey on automatic test data generation

Jon Edvardsson — 2007-08-27T08:38:43-00:00

(October 1999), pp. 21-28.

In order to reduce the high cost of manual software testing and at the same time to increase the reliability of the testing processes researchers and practitioners have tried to automate it. One of the most important components in a testing environment is an automatic test data generator --- a system that automatically generates test data for a given program. Through the years several attempts in automatic test data generations have been made. The focus of this article is program-based...

Automated test data generation using MEA-graph planning

Manish Gupta — 2008-01-10T10:25:36-00:00

Tools with Artificial Intelligence, 2004. ICTAI 2004. 16th IEEE International Conference on (2004), pp. 174-182.

With the rapid growth in the development of modern and sophisticated software applications, such as multimodal distributed systems, the complexity of software development processes has increased enormously, posing an urgent need for automation of some of these processes. One of the key software development process is system testing. In This work, we evaluate the potential application of AI planning techniques in automating the testing process. We propose a framework for an automated planning system (APS) for applying AI planning techniques for automated testing of a software module. Using a comprehensive example, we demonstrate how the MEA-Graphplan (means-ends analysis graphplan) algorithm can be used to automatically generate test data (sequence of steps or actions) to transform the system from the current state to some desired goal state. MEA-Graph planning might prove to be computationally more efficient and effective than basic graph planning technique because here the planning graph is expanded in a goal-oriented manner using regression-matching graph constructed by regressing goals over actions that can overcome the problem of state-space explosion during graph expansion phase of the planning.

Artificial Intelligence: A Modern Approach

Stuart Russell — 2005-03-04T08:43:21-00:00

(20 December 2002)

The long-anticipated revision of this best-selling book offers the most comprehensive, up-to-date introduction to the theory and practice of artificial intelligence. Intelligent Agents. Solving Problems by Searching. Informed Search Methods. Game Playing. Agents that Reason Logically. First-order Logic. Building a Knowledge Base. Inference in First-Order Logic. Logical Reasoning Systems. Practical Planning. Planning and Acting. Uncertainty. Probabilistic Reasoning Systems. Making Simple Decisions. Making Complex Decisions. Learning from Observations. Learning with Neural Networks. Reinforcement Learning. Knowledge in Learning. Agents that Communicate. Practical Communication in English. Perception. Robotics. For those interested in artificial intelligence.

MBP: a Model Based Planner

P Bertoli — 2007-06-21T10:48:18-00:00

(2001)

The Model Based Planner (MBP) is a system for planning in non-deterministic domains. It can generate plans automatically to solve various planning problems, like conformant planning, planning under partial observability, and planning for temporally extended goals. Moreover, MBP can validate plans, and offers a variety of simulation functionalities for plans and domains. MBP is based on Symbolic Model Checking techniques, and Binary Decision Diagrams (BDDs), that provide a practical solution to...

Planning as Satisfiability

Henry Kautz — 2006-05-13T01:55:22-00:00

(1992), pp. 359-363.

We develop a formal model of planning based on satisfiability rather than deduction. The satisfiability approach not only provides a more flexible framework for stating different kinds of constraints on plans, but also more accurately reflects the theory behind modern constraint-based planning systems. Finally, we consider the computational characteristics of the resulting formulas, by solving them with two very different satisfiability testing procedures. 1 Introduction Planning has...

AI planning: systems and techniques

James Hendler — 2008-07-13T14:20:43-00:00

(1990)

This article reviews research in the development of plan generation systems. Our goal is to familiarize the reader with some of the important problems that have arisen in the design of planning systems and to discuss some of the many solutions that have been developed in the over 30 years of research in this area. In this article, we broadly cover the major ideas in the field of AI planning and show the direction in which some current research is going. We define some of the terms commonly used in the planning literature, describe some of the basic issues coming from the design of planning systems, and survey results in the area. Because such tasks are virtually never ending, and thus, any finite document must be incomplete, we provide references to connect each idea to the appropriate literature and allow readers access to the work most relevant to their own research or applications.

A Survey on Case-Based Planning

Luca Spalzzi — 2007-06-13T18:06:05-00:00

Artificial Intelligence Review, Vol. 16, No. 1. (2001), pp. 3-36.

Case-based planning is the reuse of past successful plansin order to solve new planning problems.This paper presents a survey of case-based planning, in terms ofits historical roots, underlying foundations, methods andtechniques currently used, limitations, and future trends.Several authors have given overviews on case-based reasoningand specific topics such as case retrieval, case adaptation,and learning. This overview differs in focus.Its aim is to emphasize the case-based approach to planning,its methodological issues, and its relation to classical planningand the other kinds of case-based reasoning.It also provides some reference models.

Improving modeling of other agents using stereotypes and compactification of observations

J Denzinger — 2007-07-04T15:04:36-00:00

Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004. Proceedings of the Third International Joint Conference on (2004), pp. 1414-1415.

Coach planning with opponent models for distributed execution

Riley — 2006-09-22T21:22:20-00:00

Autonomous Agents and Multi-Agent Systems, Vol. 13, No. 3. (November 2006), pp. 293-325.

Opponent Modeling in Real-Time Strategy Games

Frederik Schadd — 2008-04-02T14:15:52-00:00

(2007), pp. 61-68.

KickOffTUG Erweiterung des Weltmodells. Bakkalaureatsarbeit

Máté Wolfram — 2007-09-19T09:16:59-00:00

(2007)

Understanding Planning Tasks

Malte Helmert — 2008-06-28T11:48:49-00:00

No. 4929/2008. (23 January 2008)

FLECS: Planning with a Flexible Commitment Strategy

Manuela Veloso — 2008-06-27T14:36:45-00:00

Journal of Artificial Intelligence Research, Vol. 3 (1995), pp. 25-52.

There has been evidence that least-commitment planners can efficiently handle planning problems that involve difficult goal interactions. This evidence has led to the common belief that delayed-commitment is the "best" possible planning strategy. However, we recently found evidence that eager-commitment planners can handle a variety of planning problems more efficiently, in particular those with difficult operator choices. Resigned to the futility of trying to find a universally successful...

Efficient Decision-Theoretic Planning: Techniques and Empirical Analysis

Peter Haddawy — 2008-06-27T14:31:43-00:00

pp. 229-236.

This paper discusses techniques for performing efficient decision-theoretic planning. We give an overview of the drips decisiontheoretic refinement planning system, which uses abstraction to efficiently identify optimal plans. We present techniques for automatically generating search control information, which can significantly improve the planner's performance. We evaluate the efficiency of drips both with and without the search control rules on a complex medical planning problem and compare...

Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search

Henry Kautz — 2006-03-02T19:21:04-00:00

(1996), pp. 1194-1201.

Planning is a notoriously hard combinatorial search problem. In many interesting domains, current planning algorithms fail to scale up gracefully. By combining a general, stochastic search algorithm and appropriate problem encodings based on propositional logic, we are able to solve hard planning problems many times faster than the best current planning systems. Although stochastic methods have been shown to be very effective on a wide range of scheduling problems, this is the first...

Unifying classical planning approaches

S Kambhampati — 2008-06-27T14:28:14-00:00

(1996)

State space and plan space planning approaches have traditionally been seen as fundamentally different and competing approaches to domain-independent planning. We present a plan representation and a generalized algorithm template, called UCP, for unifying these classical planning approaches within a single framework. UCP models planning as a process of refining a partial plan. The alternative approaches to planning are cast as complementary refinement strategies operating on the same...

Efficient BDD-Based Planning for Non-Deterministic Fault-Tolerant, and Adversarial Domains

Rune Jensen — 2008-06-27T14:27:07-00:00

Automated planning considers selecting and sequencing actions in order to change the state of a discrete system from some initial state to some goal state. This problem is fundamental in a wide range of industrial and academic fields including robotics, automation, embedded systems, and operational research.

Systematic Nonlinear Planning

David Mcallester — 2008-06-27T14:25:34-00:00

Vol. 2 (1991), pp. 634-639.

This paper presents a simple, sound, complete, and systematic algorithm for domain independent STRIPS planning. Simplicity is achieved by starting with a ground procedure and then applying a general, and independently verifiable, lifting transformation. Previous planners have been designed directly as lifted procedures. Our ground procedure is a ground version of Tate's NONLIN procedure. In Tate's procedure one is not required to determine whether a prerequisite of a step in an unfinished plan...

An Introduction to Least Commitment Planning

Daniel Weld — 2006-04-20T13:46:32-00:00

AI Magazine, Vol. 15, No. 4. (1994), pp. 27-61.

Recent developments have clarified the process of generating partially ordered, partially specified sequences of actions whose execution will achive an agent's goal. This paper summarizes a progression of least commitment planners, starting with one that handles the simple strips representation, and ending with one that manages actions with disjunctive precondition, conditional effects and universal quantification over dynamic universes. Along the way we explain how Chapman's formulation of...

Planning as search: a quantitative approach

Richard Korf — 2008-06-27T09:09:27-00:00

Artif. Intell., Vol. 33, No. 1. (September 1987), pp. 65-68.

Strips: A new approach to the application of theorem proving to problem solving

Richard Fikes — 2008-06-27T09:07:13-00:00

Artificial Intelligence, Vol. 2, No. 3-4. ( 1971), pp. 189-208.

We describe a new problem solver called STRIPS that attempts to find a sequence of operators in a space of world models to transform a given initial world model in which a given goal formula can be proven to be true. STRIPS represents a world model as an arbitrary collection in first-order predicate calculus formulas and is designed to work with models consisting of large numbers of formula. It employs a resolution theorem prover to answer questions of particular models and uses means-ends analysis to guide it to the desired goal-satisfying model.

Planning for conjunctive goals

David Chapman — 2008-06-27T09:05:46-00:00

Artificial Intelligence, Vol. 32, No. 3. (July 1987), pp. 333-377.

The problem of achieving conjunctive goals has been central to domain-independent planning research; the nonlinear constraint-posting approach has been most successful. Previous planners of this type have been complicated, heuristic, and ill-defined. I have combined and distilled the state of the art into a simple, precise, implemented algorithm (TWEAK) which I have proved correct and complete. I analyze previous work on domain-independent conjunctive planning; in retrospect it becomes clear that all conjunctive planners, linear and nonlinear, work the same way. The efficiency and correctness of these planners depends on the traditional add/delete-list representation for actions, which drastically limits their usefulness. I present theorems that suggest that efficient general purpose planning with more expressive action representations is impossible, and suggest ways to avoid this problem.