Specifying and computing preferred plans

In this paper, we address the problem of specifying and computing preferred plans using rich, qualitative, user preferences. We propose a logical language for specifying preferences over the evolution of states and actions associated with a plan. We provide a semantics for our first-order preference language in the situation calculus, and prove that progression of our preference formulae preserves this semantics. This leads to the development of PPlan, a bounded best-first search planner that computes preferred plans. Our preference language is amenable to integration with many existing planners, and beyond planning, can be used to support a diversity of dynamical reasoning tasks that employ preferences.     

John McCarthy's legacy

This special issue is dedicated to John McCarthy, founding father of Artificial Intelligence. It contains a collection of recent contributions to the field of knowledge representation and reasoning, a field that McCarthy founded and that has been a main focus of his research during the last half century. In this introductory article, we survey some of McCarthy's major contributions to the field of knowledge representation and reasoning, and situate the papers in this special issue in the context of McCarthy's previous work.     

Toward behavioral intelligence in the Semantic Web

Realizing the Web's full potential will require the development and support of agents that function as schedulers, planners, and searchers who, with minimal direction, can serve as an omnipresent staff of advisers, secretaries, brokers, and research assistants. Electronic commerce has brought this capability tantalizingly near. Organizations and individuals have connected an enormous variety of products and services to the Internet, making them accessible to other programs through simple communication protocols. Now the AI community must determine how it can build intelligent agents to exploit these services. One strategy would change the Web itself, making it accessible to existing AI modeling, and reasoning techniques. In this semantic Web, service and content providers would mark pages in accordance with standardized conventions designed to reduce ambiguity and make automated reasoning easier. The paper considers the development of a distributed intelligence and bringing agents to the Web. It discusses DAML-S which provides support for composite services, combinations of simpler services, or behaviors, and the coordination mechanisms, or reactive plans, used to combine those behaviors.     

Qualitative data modeling: application of a mechanism for interpreting graphical data

This paper describes a qualitative technique for interpreting graphical data. Given a set of numerical observations regarding the behaviour of a system, its attributes can be determined by plotting the data and qualitatively comparing the shape of the resulting graph with graphs of system behaviour models. Qualitative data modeling incorporates techniques from pattern recognition and qualitative reasoning to characterize observed data, generate hypothetical interpretations, and select models that best fit the shape of the data. Domain-specific knowledge may be used to substantiate or refute the likelihood of hypothesized interpretations. The basic data modeling technique is domain independent and is applicable to a wide range of problems. It is illustrated here in the context of a knowledge-based system for well test interpretation.     

A heuristic search approach to planning with temporally extended preferences

Planning with preferences involves not only finding a plan that achieves the goal, it requires finding a preferred plan that achieves the goal, where preferences over plans are specified as part of the planner's input. In this paper we provide a technique for accomplishing this objective. Our technique can deal with a rich class of preferences, including so-called temporally extended preferences (TEPs). Unlike simple preferences which express desired properties of the final state achieved by a plan, TEPs can express desired properties of the entire sequence of states traversed by a plan, allowing the user to express a much richer set of preferences. Our technique involves converting a planning problem with TEPs into an equivalent planning problem containing only simple preferences. This conversion is accomplished by augmenting the inputed planning domain with a new set of predicates and actions for updating these predicates. We then provide a collection of new heuristics and a specialized search algorithm that can guide the planner towards preferred plans. Under some fairly general conditions our method is able to find a most preferred plan—i.e., an optimal plan. It can accomplish this without having to resort to admissible heuristics, which often perform poorly in practice. Nor does our technique require an assumption of restricted plan length or make-span. We have implemented our approach in the HPlan-P planning system and used it to compete in the 5th International Planning Competition, where it achieved distinguished performance in the Qualitative Preferences track.     

Generating effective tests for concurrent programs via AI automated planning techniques

Testing concurrent programs is a challenging problem due to interleaving explosion: even for a fixed set of inputs, there is a huge number of concurrent runs that need to be tested to account for scheduler behavior. Testing all possible schedules is not practical. Consequently, most effective testing algorithms only test a select subset of runs. For example, limiting testing to runs that contain data races or atomicity violations has been shown to capture a large proportion of concurrency bugs. In this paper we present a general approach to concurrent program testing that is based on techniques from artificial intelligence (AI) automated planning. We propose a framework for predicting concurrent program runs that violate a collection of generic correctness specifications for concurrent programs, namely runs that contain data races, atomicity violations, or null-pointer dereferences. Our prediction is based on observing an arbitrary run of the program, and using information collected from this run to model the behavior of the program, and to predict new runs that contain bugs with one of the above noted violation patterns. We characterize the problem of predicting such new runs as an AI sequential planning problem with the temporally extended goal of achieving a particular violation pattern. In contrast to many state-of-the-art approaches, in our approach feasibility of the predicted runs is guaranteed and, therefore, all generated runs are fully usable for testing. Moreover, our planning-based approach has the merit that it can easily accommodate a variety of violation patterns which serve as the selection criteria for guiding search in the state space of concurrent runs. This is achieved by simply modifying the planning goal. We have implemented our approach using state-of-the-art AI planning techniques and tested it within the Penelope concurrent program testing framework [35]. Nevertheless, the approach is general and is amenable to a variety of program testing frameworks. Our experiments with a benchmark suite showed that our approach is very fast and highly effective, finding all known bugs.     

Birdsong recognition using backpropagation and multivariatestatistics

An investigation has been made of bird species recognition using recordings of birdsong. Six species of birds native to Manitoba were chosen: song sparrows, fox sparrows, marsh wrens, sedge wrens, yellow warblers, and red-winged blackbirds. These species exhibit overlapping characteristics in terms of frequency content, song components, and length of songs. Songs from multiple individuals in each of these species were employed, with discernible recording noise such as tape hiss and, in some cases, other competing songs in the background. These songs were analyzed using backpropagation learning in two-layer perceptrons, as well as methods from multivariate statistics that included principal components and quadratic discriminant analysis. Preprocessing methods included linear predictive coding and windowed Fourier transforms. Generalization performance ranged from 82-93 % correct identification, with the lower figures corresponding to smaller networks employing more preprocessing for dimensionality reduction. At the same time, the computational requirements were significantly reduced in this case     

Semantic Web services

The authors propose the markup of Web services in the DAML family of Semantic Web markup languages. This markup enables a wide variety of agent technologies for automated Web service discovery, execution, composition and interoperation. The authors present one such technology for automated Web service composition.