When creating algorithms or systems that are supposed to be used by people, we should be able to adopt a “binocular” view of users’ interaction with intelligent systems: a view that regards the design of interaction and the design of intelligent algorithms as interrelated parts of a single design problem. This special issue offers a coherent set of articles on two levels of generality that illustrate the binocular view and help readers to adopt it.

This case study article describes the iterative design process of an adaptive, mixed-initiative calendaring tool with embedded artificial intelligence.  We establish the specific types of assistance in which the target user population expressed interest, and we highlight our findings regarding the scheduling practices and the reminding preferences of these users.  These findings motivated the redesign and enhancement of our intelligent system.  Lessons learned from the study—namely, highlighting the merits of usability toward widespread adoption and retention, and that simple problems that perhaps do not necessitate complex AI-based solutions should not go unattended merely due to their inherent simplicity—conclude the article, along with a discussion of the importance of the iterative design process for any user adaptive system.

Soft goals extend the classical model of planning with a simple model of preferences. The best plans are then not the ones with least cost but the ones with maximum utility, where the utility of a plan is the sum of the utilities of the soft goals achieved minus the plan cost. Finding plans with high utility appears to involve two linked problems: choosing a subset of soft goals to achieve and finding a low-cost plan to achieve them. New search algorithms and heuristics have been developed for planning with soft goals, and a new track has been introduced in the International Planning Competition (IPC) to test their performance. In this note, we show however that these extensions are not needed: soft goals do not increase the expressive power of the basic model of planning with action costs, as they can easily be compiled away. We apply this compilation to the problems of the net-benefit track of the most recent IPC, and show that optimal and satisficing cost-based planners do better on the compiled problems than optimal and satisficing net-benefit planners on the original problems with explicit soft goals. Furthermore, we show that penalties, or negative preferences expressing conditions to avoid, can also be compiled away using a similar idea.

This paper presents several new tractability results for planning based on macros. We describe an algorithm that optimally solves planning problems in a class that we call inverted tree reducible, and is provably tractable for several subclasses of this class. By using macros to store partial plans that recur frequently in the solution, the algorithm is polynomial in time and space even for exponentially long plans. We generalize the inverted tree reducible class in several ways and describe modifications of the algorithm to deal with these new classes. Theoretical results are validated in experiments.

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.

Probabilistic sampling methods have become very popular to solve single-shot path planning problems. Rapidly-exploring Random Trees (RRTs) in particular have been shown to be efficient in solving high dimensional problems. Even though several RRT variants have been proposed for dynamic replanning, these methods only perform well in environments with infrequent changes. This paper addresses the dynamic path planning problem by combining simple techniques in a multi-stage probabilistic algorithm. This algorithm uses RRTs for initial planning and informed local search for navigation. We show that this combination of simple techniques provides better responses to highly dynamic environments than the RRT extensions.

Probabilistic sampling methods have become very popular to solve single-shot path planning problems. Rapidly-exploring Random Trees (RRTs) in particular have been shown to be very efficient in solving high dimensional problems. Even though several RRT variants have been proposed to tackle the dynamic replanning problem, these methods only perform well in environments with infrequent changes. This paper addresses the dynamic path planning problem by combining simple techniques in a multi-stage probabilistic algorithm. This algorithm uses RRTs as an initial solution, informed local search to fix unfeasible paths and a simple greedy optimizer. The algorithm is capable of recognizing when the local search is stuck, and subsequently restart the RRT. We show that this combination of simple techniques provides better responses to a highly dynamic environment than the dynamic RRT variants.