Sensor-to-symbol conversion lies at the heart of all embedded intelligent systems. The everyday world occupied by human stakeholders is dominated by objects that have symbolic labels. For an embedded intelligent system to operate in such a world it must also be able to segment its sensory stream into objects and label those objects appropriately. It is our position that development of a consistent and flexible sensor-to-symbol reasoning system (or architecture) is a key component of embedded intelligence.

Community health worker programs provide healthcare to those living outside the financial and physical reach of the standard health infrastructure. These programs are particularly prevalent in low resource regions. Frequently such programs involve community health workers making household visits across a significant geographical area. We suggest that this problem can be posed as a formal routing and scheduling problem, and to use techniques developed from solving the travelling salesman problem with time windows. In addition, household visits can generate a series of future follow up visits, a feature not often handled in the combinatorial scheduling and routing literature. We present the basic problem and outline potential research directions.

We study the problem of allocating stocks to dark pools. We propose and analyze an optimal approach for allocations, if continuous-valued allocations are allowed. We also propose a modification for the case when only integer-valued allocations are possible. We extend the previous work on this problem (Ganchev et al., 2009) to adversarial scenarios, while also improving on their results in the iid setup. The resulting algorithms are efficient, and perform well in simulations under stochastic and adversarial inputs.

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.

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.

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.

This document is a thesis on the subject of single-agent on-line path planning in continuous,unpredictable and highly dynamic environments. The problem is finding and traversing a collision-free path for a holonomic robot, without kinodynamic restrictions, moving in an environment with several unpredictably moving obstacles or adversaries. The availability of perfect information of the environment at all times is assumed. Several static and dynamic variants of the Rapidly Exploring Random Trees (RRT) algorithm are explored, as well as an evolutionary algorithm for planning in dynamic environments called the Evolutionary Planner/Navigator. A combination of both kinds of algorithms is proposed to overcome shortcomings in both, and then a combination of a RRT variant for initial planning and informed local search for navigation, plus a simple greedy heuristic for optimization. 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 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.