It is well known that the planning problem (namely, the probl em of obtaining a valid sequence of transformations that moves a sys tem from an initial state to a goal state) is intractable in general [3]. However, it is widely believed that many real-life problems have a particu lar structure, and that by exploiting this structure general planners will be able to efficiently handle more meaningful problems. One of the most fruitful tools researchers have been using to characterize structure in planning problems is the so called causal graph ([6]). In short, the causal graph of a problem instance is a graph that c aptures the degree of interdependence among the state variables of the p roblem.The causal graph has been used both as a tool for describing tract able subclasses of planning problems (e.g., [7], [2], [4]) and as a ke y property which algorithms that adress the general planning problem take in to consideration [5]. In the present work we show that solving planning domains whe re the causal graph is a polytree (that is, the underlying undir ected graph is acyclic) is NP-complete, even if we restrict to domains wi th binary variables and unary operators. This result closes the compl exity gap that appears in [4], where it is shown that plan existence is NP-co mplete for planning domains with singly connected causal graphs, and t hat plan generation is polynomial for planning domains with polytre e causal graphs of bounded indegree. Additionally, it is known that solving unary operator plann ing problems on binary variables is essentially equivalent to solvi ng dominance queries for binary-valued CP-nets (see [1]). Under this ref ormulation the causal graph becomes the CP-net, so the present work also sho ws that dominance testing for binary-valued polytree CP-nets is NP -complete.

The ever higher complexity of manufacturing systems, continually shortening life cycles of products and their increasing variety, as well as the unstable market situation of the recent years require introducing grater flexibility and responsiveness to manufacturing processes. From this perspective, one of the critical manufacturing tasks, which traditionally attract significant attention in both academia and the industry, but which have no satisfactory universal solution, is production scheduling. This paper proposes an approach based on genetics-based machine learning (GBML) to treat the problem of flow shop scheduling. By the approach, a set of scheduling rules is represented as an individual of genetic algorithms, and the fitness of the individual is estimated based on the makespan of the schedule generated by using the rule-set. A concept of the interactive software environment consisting of a simulator and a GBML simulation engine is introduced to support human decision-making during scheduling. A pilot study is underway to evaluate the performance of the GBML technique in comparison with other methods (such as Johnson's algorithm and simulated annealing) while completing test examples.

We extend the 0-approximation of sensing actions and incomplete information in [Son and Baral 2000] to action theories with static causal laws and prove its soundness with respect to the possible world semantics. We also show that the conditional planning problem with respect to this approximation is NP-complete. We then present an answer set programming based conditional planner, called ASCP, that is capable of generating both conformant plans and conditional plans in the presence of sensing actions, incomplete information about the initial state, and static causal laws. We prove the correctness of our implementation and argue that our planner is sound and complete with respect to the proposed approximation. Finally, we present experimental results comparing ASCP to other planners.

Path planning and obstacle avoidance are the two major issues in any navigation system. Wavefront propagation algorithm, as a good path planner, can be used to determine an optimal path. Obstacle avoidance can be achieved using possibility theory. Combining these two functions enable a robot to autonomously navigate to its destination. This paper presents the approach and results in implementing an autonomous navigation system for an indoor mobile robot. The system developed is based on a laser sensor used to retrieve data to update a two dimensional world model of therobot environment. Waypoints in the path are incorporated into the obstacle avoidance. Features such as ageing of objects and smooth motion planning are implemented to enhance efficiency and also to cater for dynamic environments.

The quest for robust heuristics that are able to solve more than one problem is ongoing. In this paper, we present, discuss and analyse a technique called Evolutionary Squeaky Wheel Optimisation and apply it to two different personnel scheduling problems. Evolutionary Squeaky Wheel Optimisation improves the original Squeaky Wheel Optimisation's effectiveness and execution speed by incorporating two extra steps (Selection and Mutation) for added evolution. In the Evolutionary Squeaky Wheel Optimisation, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The aim of the Analysis step is to identify below average solution components by calculating a fitness value for all components. The Selection step then chooses amongst these underperformers and discards some probabilistically based on fitness. The Mutation step further discards a few components at random. Solutions can become incomplete and thus repairs may be required. The repairs are carried out by using the Prioritization to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, improvement in the Evolutionary Squeaky Wheel Optimisation is achieved by selective solution disruption mixed with interative improvement and constructive repair. Strong experimental results are reported on two different domains of personnel scheduling: bus and rail driver scheduling and hospital nurse scheduling.

Nurse rostering is a complex scheduling problem that affects hospital personnel on a daily basis all over the world. This paper presents a new component-based approach with evolutionary eliminations, for a nurse scheduling problem arising at a major UK hospital. The main idea behind this technique is to decompose a schedule into its components (i.e. the allocated shift pattern of each nurse), and then to implement two evolutionary elimination strategies mimicking natural selection and natural mutation process on these components respectively to iteratively deliver better schedules. The worthiness of all components in the schedule has to be continuously demonstrated in order for them to remain there. This demonstration employs an evaluation function which evaluates how well each component contributes towards the final objective. Two elimination steps are then applied: the first elimination eliminates a number of components that are deemed not worthy to stay in the current schedule; the second elimination may also throw out, with a low level of probability, some worthy components. The eliminated components are replenished with new ones using a set of constructive heuristics using local optimality criteria. Computational results using 52 data instances demonstrate the applicability of the proposed approach in solving real-world problems.

Despite the extensive development of first-principles planning in recent years, planning applications are still primarily developed using knowledge-based planners which can exploit domain-specific heuristics and weaker domain models.  Hierarchical Task Network (HTN) planners capture domain-specific heuristics for more efficient search, accommodate incomplete causal models, and can be used to enforce standard operating procedures.  Unfortunately, we do not have semantics for the methods or tasks that make up HTN models, that help evaluate the correctness of methods, or to build a reliable executive for HTN plans.  This paper fills the gap by providing a well-defined semantics for the methods and plans of SHOP2, a state-of-the-art HTN planner.  The semantics are defined in terms of concurrent golog (ConGolog) and the situation calculus.  We provide a proof of equivalence between the plans generated by SHOP2 and the action sequences of the ConGolog semantics.  We show how the semantics reflects the distinction between plan-time and execution-time, and provide some simple examples showing how the semantics can support method verification.  The semantics provide an implementation-neutral specification for an executive, showing how an executive must treat the plans SHOP2 generates in order to enforce the expected behaviors.  Future directions include automated verification of method specifications, automatically generating plan monitors, and plan revision and repair.

Temporally expressive planning, an important class of temporal planning, has attracted much attention lately. Temporally expressive planning is difficult; few existing planners can solve them, as they have highly concurrent actions. We propose an optimal approach to temporally expressive planning based on a SAT formulation of the problem, finding solutions with the shortest time spans. Our experiments on several temporally expressive domains showed that our planner is able to optimally solve many instances in a reasonable amount of time, comparing favorably to existing temporally expressive planners. Our second result is a temporally expressive planning problem formulation of the Peer-to-Peer (P2P) network communications. In addition to demonstrating a better performance of our new method than the only existing temporally expressive planners on several temporally expressive problem domains, we apply our new planner to find optimal communication schedules for P2P networks. Our results will be potentially useful for designing efficient communication protocols in P2P networks.

This paper explores the use of an oft-ignored information source in heuristic search: a search-distance-to-go estimate. Operators frequently have different costs and cost-to-go is not the same as search-distance-to-go.  We evaluate two previous proposals: dynamically weighted A* and A* epsilon.  We present a revision to dynamically weighted A* that improves its performance substantially in domains where the search does not progress uniformly towards solutions, and particularly in certain temporal planning problems.  We show how to incorporate distance estimates into weighted A* and improve its performance in several domains. Both approaches lead to dramatic performance increases in popular benchmark domains.

This paper proposes an iterative improvement approach for solving the Resource Constraint Project Scheduling Problem with Time-Windows (RCPSP/max), a well-known and challenging NP-hard scheduling problem. The algorithm is based on Iterative Flattening Search (IFS), an effective heuristic strategy for solving multi-capacity optimization scheduling problems. Given an initial solution, IFS iteratively performs two-steps: a relaxation-step , that randomly removes a subset of solution constraints and a solving-step , that incrementally recomputes a new solution. At the end, the best solution found is returned. The main contribution of this paper is the extension to RCPSP/max of the IFS optimization procedures developed for solving scheduling problems without time-windows. An experimental evaluation performed on medium-large size and web-available benchmark sets confirms the effectiveness of the proposed procedures. In particular, we have improved the average quality w.r.t. the current bests, while discovering three new optimal solutions, thus demonstrating the general efficacy of IFS.