Search

We study a planning problem based on Plotting, a tile-matching puzzle video game published by Taito in 1989. The objective of this turn-based game is to remove a target number of coloured blocks from a grid by sequentially shooting blocks into the same grid. Plotting features complex transitions after every shot: various blocks are affected directly, while others can be indirectly affected by gravity. We consider modelling and solving Plotting from two perspectives. The puzzle is naturally cast as an AI Planning problem and we first discuss modelling the problem using the Planning Domain Definition Language (PDDL). We find that a model in which planning actions correspond to player actions is inefficient with a grounding-based state-of-the-art planner. However, with a more fine-grained action model, where each change of a block is a planning action, solving performance is dramatically improved. We also describe two lifted constraint models, able to capture the inherent complexities of Plotting and enabling the application of efficient solving approaches from SAT and CP. Our empirical results with these models demonstrates that they can compete with, and often exceed, the performance of the dedicated planning solvers, suggesting that the richer languages available to constraint modelling can be of benefit when considering planning problems with complex changes of state. CP and SAT solvers solved almost all of the largest and most challenging instances within 1 hour, whereas the best planning approach solved approximately 30%. Finally, the flexibility provided by the constraint models allows us to easily curate interesting levels for human players. [ABSTRACT FROM AUTHOR]

Deep learning (DL) is a branch of machine learning that uses deep neural networks (DNNs) to extract knowledge from raw data. DL techniques have been used successfully in many intelligence domains, such as general approximation, computer vision, pattern recognition, and many more. Planning problems with small search space can be solved by exhaustive exploration of the search space, whereas the big search space of some problems exposes the search space explosion due to computational limitations. This subject motivates us to propose an approach using DL techniques for solving such planning problems. The proposed approach tries to learn the knowledge about the application order of actions, before solving the given (main) planning problem. Actually, it reduces the size of the given planning problem such that it can be solved by exhaustive exploration of the search space. After solving the reduced problem successfully, a DNN is learned from the explored search space. The proposed approach then employs the learned DNN to solve the given planning problem. The proposed approach deals with the planning problems specified through graph transformations language because of its superiorities compared to planning domain definition languages. The main contribution of the proposed approach is that it uses DL techniques, for the first time, to solve planning problems specified through graph transformations. Based on experimental results, the proposed approach outperforms state-of-the-art techniques in terms of execution speed, accuracy, and generating short-length plans with the exploration of lower states. [ABSTRACT FROM AUTHOR]

A service robot needs integration of symbolic reasoning for high-level task planning and geometric computation for low-level motion planning to provide services in an everyday human-living environment. For this purpose, one may develop individual modules for object recognition, knowledge inference, task planning, and motion planning, which requires a system that integrates them to provide services autonomously. In this paper, we propose a combined task-motion planning system implemented using existing open-source libraries. We implemented an action library module that specifies the relationship between the compound actions that are modeled in an AI planning language to enable abstract reasoning and the primitive actions that can be geometrically verified its feasibility. This serves as an interface between the two levels by providing a rule in which a compound action sequence obtained from task planning at the symbolic level is decomposed into a primitive action sequence capable of motion planning at the geometric level. In addition, we defined the relationship between the two types of actions in a hierarchical structure and added conditional clauses according to the task states, so that primitive actions that need to be additionally performed are automatically added to the action sequence during decomposition. This procedure enables the robot to successfully perform the task in response to an unintended change in the environment. We establish a task domain where a robot delivers an object to a human user in unexpected situations and verify the proposed method under dynamic simulation environments. [ABSTRACT FROM AUTHOR]

Virtual reality simulation has had a significant impact on training of psychomotor surgical skills, yet there is still a lack of work on its use to teach surgical decision making. This is particularly noteworthy given the recognized importance of decision making in achieving positive surgical outcomes. With the objective of filling this gap, we have developed a system for teaching surgical decision making in the field of endodontics, by integrating a virtual reality simulation environment with a conversational intelligent tutor. This work presents SDMentor (Surgical Decision-making Mentor) – the first intelligent tutoring system for teaching surgical decision making. In this paper we focus on presenting the intelligent tutoring component of the training system. The design of the system and the teaching approaches are driven by information gained from an observational study of clinical teaching sessions. The tutoring system represents surgical actions and the procedure using a variant of the planning domain definition language (PDDL). Tutorial interaction places emphasis on teaching the rationale for decisions, as well as aspects of situation awareness. We evaluated the quality of the tutorial content by comparing it with tutorial feedback from ten experienced human tutors. We had three expert dental instructors rate the appropriateness of the tutorial feedback given by the human tutors as well as SDMentor over 20 scenarios. Bayesian analysis showed that tutoring interventions of SDMentor were significantly better than interventions by human tutors. To determine whether the expert scores may have been influenced by raters' knowledge of whether interventions came from human tutors or SDMentor, we carried out a type of Turing test. Results show that the expert raters were able to correctly guess which interventions came from SDMentor only 15% of the time, compared to a random baseline accuracy of 9%. [ABSTRACT FROM AUTHOR]

A completeness threshold is required to guarantee the completeness of planning as satisfiability, and bounded model checking of safety properties. We investigate completeness thresholds related to the diameter of the underlying transition system. A valid threshold, the diameter is the maximum element in the set of lengths of all shortest paths between pairs of states. The diameter is not calculated exactly in our setting, where the transition system is succinctly described using a (propositionally) factored representation. Rather, an upper bound on the diameter is calculated compositionally, by bounding the diameters of small abstract subsystems, and then composing those. We describe our formal verification in HOL4 of compositional algorithms for computing a relatively tight upper bound on the system diameter. Existing compositional algorithms are characterised in terms of the problem structures they exploit, including acyclicity in state-variable dependencies, and acyclicity in the state space. Such algorithms are further distinguished by: (1) whether the bound calculated for abstractions is the diameter, sublist diameter or recurrence diameter, and (2) the “direction” of traversal of the compositional structure, either top-down or bottom-up. As a supplement, we publish our library—now over 14k lines—of HOL4 proof scripts about transition systems. That shall be of use to future related mechanisation efforts, and is carefully designed for compatibility with hybrid systems. [ABSTRACT FROM AUTHOR]

Composite models in Decision Support Systems (DSS) are combinations of model functions to solve complex decision problems. They must be executed successfully to obtain the desired results. Unfortunately, faults may happen during its execution due to the dynamic networks or the information asymmetry between developers and users. Therefore, designing effective failure recovery mechanism to ensure the reliability of the composite model execution is essential. Progress has been made in the web service composition field to obtain limited failure recovery capabilities, but not fully applicable to composite models since model services are informational services in essence which do not change the world conditions. This paper proposes a unified framework, integrated with a process ontology and multiple recovery strategies that can provide valuable failure recovery recommendations intelligently. The recovery strategies have been greatly enhanced in providing greater failure recovery capability. Feasibility and efficiency of this framework have been illustrated and tested. [ABSTRACT FROM AUTHOR]

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 []. 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. [ABSTRACT FROM AUTHOR]

This paper proposes a novel approach based on the planning-graph to solve the top-k QoS-aware automatic composition problem of semantic Web services. The approach includes three sequential stages: a forward search stage to generate a planning-graph to reduce the search space of the following two stages greatly, an optimal local QoS calculating stage to compute all the optimal local QoS values of services in the planning, and a backward search stage to find the top-K composed services with optimal QoS values according to the planning-graph and the optimal QoS value. In order to validate the approach, experiments are carried out based on the test sets offered by the WS-Challenge competition 2009. The results show that the approach can find the same optimal solution as the champion system from the competition but also can provide more alternative solutions with the optimal QoS for users. [ABSTRACT FROM AUTHOR]

In this paper, novel ideas are presented for solving the automated web service composition problem. Some of the possible real world problems such as partial observability of the environment, nondeterministic effects of web services and service execution failures are solved through a dynamic planning approach. The proposed approach is based on a novel AI planner that is designed for working in highly dynamic environments under time constraints, namely Simplanner. World altering service calls are done according to the WS-Coordination and WS-Business Activity web service transaction specifications in order to physically recover from failure situations and prevent the undesired side effects of the aborted web service composition efforts. [ABSTRACT FROM AUTHOR]

Legacy application design models, which are still widely used for developing context-aware applications, incur important limitations. Firstly, embedding contextual dependencies in the form of if–then rules specifying how applications should react to context changes is impractical to accommodate the large variety of possibly even unanticipated context types and their values. Additionally, application development is complicated and challenging, as programmers have to manually determine and encode the associations of all possible combinations of context parameters with application behaviour. In this paper we propose a framework for building context aware applications on-demand, as dynamically composed sequences of calls to services. We present the design and implementation of our system, which employs goal-oriented inferencing for assembling composite services, dynamically monitors their execution, and adapts applications to deal with contex- tual changes. We describe the failure recovery mechanisms we have implemented, allowing the deployment of the system in a non-perfect environment, and avoiding the delays inherent in re-discovering a suitable service instance. By means of experimental evaluation in a realistic infotainment application, we demonstrate the potential of the proposed solution an effective, efficient, and scalable approach. [ABSTRACT FROM AUTHOR]

Web services composition techniques are gaining momentum as the opportunity to establish reusable and versatile inter-operability applications. Many researchers propose their composition approach based on planning techniques. We propose our context aware planning method which comprises global planning and local optimization based on context information. The major technical contributions of this paper are: (1) We propose an ontology-based framework for the context-aware composition of Web services. Context model, which are structured based on OWL-S, captures the Service-related, Environment-related, and User-related context and can be used in an unambiguous, machine interpretable form. (2) We propose context-aware plan architecture and thus is more scalability and flexibility for the planning process, and thereby improving the efficiency and precision. (3) We propose a hybrid approach to build a plan corresponding to a context-aware service composition, based on global planning and local optimization, considering both the usability and adoption. We test our approach on a simple, yet realistic example, and the preliminary results demonstrate that our implementation provides a practical solution. [ABSTRACT FROM AUTHOR]

This paper presents an alternative to the 'speech acts with STRIPS' approach to implementing dialogue: a fully implemented AI planner which generates and analyses the semantics of utterances using a single linguistic act for all contexts. Using this act, the planner can model problematic conversational situations, including felicitous and infelicitous instances of bluffing, lying, sarcasm, and stating the obvious. The act has negligible effects, and its precondition can always be proved. 'Speaker maxims' enable the speaker to plan to deceive, as well as to generate implicatures, while 'hearer maxims' enable the hearer to recognise deceptions, and interpret implicatures. The planner proceeds by achieving parts of the constructive proof of a goal. It incorporates an epistemic theorem prover, which embodies a deduction model of belief, and a constructive logic. [ABSTRACT FROM AUTHOR]

We describe the modular architecture of a generic dialogue system that assists a user/operator in performing a task with a tool. This coaching system is named CALLIOPE after the Greek goddess of eloquence. It aims at being an active partner in an intelligent man-machine dialogue. The intelligent dimension of the coaching system is reflected by its ability to adapt to the user and the situation at hand. The CALLIOPE system contains an explicit user model and world model to situate its dialogue actions. A plan library allows it to follow loosely predetermined dialogue scenarios. The heart of the coaching system is an AI planning module, which plans a series of dialogue actions. We present a coherent set of three dialogue or speech actions that will make up the physical form of the man-machine communication.The use of the AI planning paradigm as a basis for man-machine interaction is motivated by research in various disciplines, as e.g., AI, Cognitive Science and Social Sciences. Starting from the man-man communication metaphor, we can view the “thinking before speaking” of a human communication partner as constructing an underlying plan which is responsible for the purposiveness, the organisation and the relevance of the communication. CALLIOPE has been fully implemented and tested on theoretical examples. At present, also three tailored versions of CALLIOPE are in operational use in different industrial application domains: operator support for remedying tasks in chemical process industry, operator support for a combined task of planning, plan execution and process control in the area of chemical process development, and thirdly decision support in production scheduling. [ABSTRACT FROM AUTHOR]

While Artificial Intelligence techniques have been applied to a variety of software engineering applications, the area of automated software testing remains largely unexplored. Yet, test cases for certain types of systems (e.g., those with command language interfaces and transaction based systems) are similar to plans. We have exploited this similarity by constructing an automated test case generator with an AI planning system at its core. We compared the functionality and output of two systems, one based on Software Engineering techniques and the other on planning, for a real application: the StorageTek robot tape library command language. From this, we showed that AI planning is a viable technique for test case generation and that the two approaches are complementary in their capabilities. [ABSTRACT FROM AUTHOR]