This paper presents an approach towards automated semantic web service composition using contingent planning. The presented planner, MAPPPA, is an anytime probabilistic planner tailor-made for web service composition problems that produces a contingent plan by integrating alternative deterministic plans previously computed from a determinized version of the original planning problem. The planner can produce each plan without disregarding the important information that each web service contains in relation to its cost and probability of alternative outcomes. MAPPPA has already been integrated into our prototype web service composition platform, MADSWAN, producing promising results.

This article presents a systematic and complete algorithm to compute all higher order exclusion relations for a propositional planning problem, that is, sets of propositions that cannot hold simultaneously at specific time points, without any bound on the order of the exclusion relations. This algorithm is proved to allow for backtrack-free plan extraction, provided that all goals have to be achieved simultaneously. In particular, levelled global consistency is achieved, i.e. all exclusion relations between propositions within each time step are computed. However, achieving levelled global consistency is impractical for most non-trivial planning problems. Indeed, as our empirical evaluation over a variety of planning problems suggests, best performance is achieved when setting a bound on the order of the computed exclusion relations and using search to extract a plan. Additional statistics extracted from our experiments shed light on the internal dynamics of Graphplan-style planners.

This paper presents a method for fast planning within arbitrary maps, through segmentation of the map into Manhattan-cohesive areas. A Manhattan-cohesive area is a connected part of the map where the optimal distance between any two points in the area is equal to their Manhattan distance. We adopt a four directions Manhattan distance, where diagonal moves are allowed. In the paper we present the method we adopted to fragmentize the map, as well the method to extract the paths. The proposed method produces nearly optimal plans quite efficiently.

This article presentsSelfPlanner, a deployed Web‐based intelligent calendar application that helps a user schedule in time and space her individual tasks. Contrary to other intelligent calendar assistants that concentrate on automating meeting scheduling,SelfPlanneremphasizes on scheduling individual tasks and events, leaving meeting arrangement for external handling. The two key features ofSelfPlanner, also critical factors for its potential broader adoption, are problem modeling and user interface.SelfPlannersupports simple, interruptible and flexible periodic tasks, arbitrary temporal domains, constraints over the parts of an interruptible task, binary constraints between tasks and preferences over their temporal domains, location references, classes of locations, time zones, etc. As for user interface,SelfPlannerintegrates with Google Calendar and a Google Maps based application, whereas it introduces an innovative way to define temporal domains, based on a combination of user‐defined reusable templates and manual editing. The core of the system is based on the Squeaky Wheel Optimization algorithm, with efficient domain‐dependent heuristics. The article is accompanied with an extensive evaluation of the system, comprising an analytic and an exploratory part. Evaluation results are very promising and suggest thatSelfPlannerconstitutes a step toward the next generation of intelligent calendar applications.

The goal of helping to automate the management of an individual's time is ambitious in terms both of knowledge engineering and of the quality of the plans produced by an AI system. Modeling an individual's activities is itself a challenge, due to the variety of activity, constraint, and preference types involved. Activities might be simple or interruptible; they might have fixed or variable durations, constraints over their temporal domains, and binary constraints between them. Activities might require the individual being at specific locations in order, whereas traveling time should be taken into account. Some activities might require exclusivity, whereas others can be overlapped with compatible concurrent activities. Finally, while scheduled activities generate utility for the individual, extra utility might result from the way activities are scheduled in time, individually and in conjunction. This article presents a rigorous, expressive model to represent an individual's activities, that is, activities whose scheduling is not contingent on any other person. Joint activities such as meetings are outside our remit; it is expected that these are arranged manually or through negotiation mechanisms and they are considered as fixed busy times in the individual's calendar. The model, formulated as a constraint optimization problem, is general enough to accommodate a variety of situations. We present a scheduler that operates on this rich model, based on the general squeaky wheel optimization framework and enhanced with domain-dependent heuristics and forward checking. Our empirical evaluation demonstrates both the efficiency and the effectiveness of the selected approach. Part of the work described has been implemented in the SelfPlanner system, a Web-based intelligent calendar application that utilizes Google Calendar.

This paper presents GRT, a domain-independent heuristic planning system for STRIPS worlds. GRT solves problems in two phases. In the pre-processing phase, it estimates the distance between each fact and the goals of the problem, in a backward direction. Then, in the search phase, these estimates are used in order to further estimate the distance between each intermediate state and the goals, guiding so the search process in a forward direction and on a best-first basis. The paper presents the benefits from the adoption of opposite directions between the preprocessing and the search phases, discusses some difficulties that arise in the pre-processing phase and introduces techniques to cope with them. Moreover, it presents several methods of improving the efficiency of the heuristic, by enriching the representation and by reducing the size of the problem. Finally, a method of overcoming local optimal states, based on domain axioms, is proposed. According to it, difficult problems are decomposed into easier sub-problems that have to be solved sequentially. The performance results from various domains, including those of the recent planning competitions, show that GRT is among the fastest planners.

This paper describes Operator Distribution Method for parallel Planning (ODMP), a parallelization method for efficient heuristic planning. The method innovates in that it parallelizes the application of the available operators to the current state and the evaluation of the successor states using the heuristic function. In order to achieve better load balancing and a lift in the scalability of the algorithm, the operator set is initially enlarged, by grounding the first argument of each operator. Additional load balancing is achieved through the reordering of the operator set, based on the expected amount of imposed work. ODMP is effective for heuristic planners, but it can be applied to planners that embody other search strategies as well. It has been applied to GRT, a domain-independent heuristic planner, and CL, a heuristic planner for simple logistics problems, and has been thoroughly tested on a set of logistics problems adopted from the AIPS-98 planning competition, giving quite promising results.