We present a case study of artificial intelligence techniques applied to the control of production printing equipment. Like many other real-world applications, this complex domain requires high-speed autonomous decision-making and robust continual operation. To our knowledge, this work represents the first successful industrial application of embedded domain-independent temporal planning. Our system handles execution failures and multi-objective preferences. At its heart is an on-line algorithm that combines techniques from state-space planning and partial-order scheduling. We suggest that this general architecture may prove useful in other applications as more intelligent systems operate in continual, on-line settings. Our system has been used to drive several commercial prototypes and has enabled a new product architecture for our industrial partner. When compared with state-of-the-art off-line planners, our system is hundreds of times faster and often finds better plans. Our experience demonstrates that domain-independent AI planning based on heuristic search can flexibly handle time, resources, replanning, and multiple objectives in a high-speed practical application without requiring hand-coded control knowledge.

Flooding protocols for wireless networks in general have been shown to be very inefficient and therefore are mainly used in network initialization or route discovery and maintenance. In this paper, we propose a framework of constrained flooding protocols. The framework incorporates a reinforcement learning kernel, a differential delay mechanism, and a constrained and probabilistic retransmission policy. This type of protocol takes the advantages of robustness from flooding, but maintains energy efficiency by constraining retransmissions. Without the use of any control packets, such a protocol adapts to the specific routing requirements of the task and the dynamic changes of the network. We analyze this framework in simulation using a real-world application in sensor networks.

Most existing routing mechanisms differ in routing objectives and routing strategies; however, all the existing routing protocols have in common that the routing objective and destination specification are fixed, and that the routing objective is incorporated only implicitly. We propose a general message specification mechanism to encode explicitly the routing destinations, constraints and objectives in messages, so that general-purpose instead of objective or destination specific routing strategies can be applied. Using general-purpose routing strategies while specifying quality-of-service (QoS) properties explicitly at the application layer in messages, QoS-aware strategies for individual messages are obtained. We also propose two frameworks of general-purpose routing strategies for this type of message specification.

We propose an approach that uses connectivity information - who is within communications range of whom - to derive the locations of nodes in a network. The approach can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. It is based on multidimensional scaling (MDS), an efficient data analysis technique that takes O(n/sup 3/) time for a network of n nodes. Unlike previous approaches, MDS takes full advantage of connectivity or distance information between nodes that have yet to be localized. Two methods are presented: a simple method that builds a global map using MDS and a more complicated one that builds small local maps and then patches them together to form a global map. Furthermore, least-squares optimization can be incorporated into the methods to further improve the solutions at the expense of additional computation. Through simulation studies on uniform as well as irregular networks, we show that the methods achieve more accurate solutions than previous methods, especially when there are few anchor nodes. They can even yield good relative maps when no anchor nodes are available.

It is often useful to know the geographic positions of nodes in a communications network, but adding GPS receivers or other sophisticated sensors to every node can be expensive. We present an algorithm that uses connectivity information who is within communications range of whom to derive the locations of the nodes in the network. The method can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. The algorithm is based on multidimensional scaling, a data analysis technique that takes O(n3) time for a network of n nodes. Through simulation studies, we demonstrate that the algorithm is more robust to measurement error than previous proposals, especially when nodes are positioned relatively uniformly throughout the plane. Furthermore, it can achieve comparable results using many fewer anchor nodes than previous methods, and even yields relative coordinates when no anchor nodes are available.

Spatial Aggregation abstracts data arising from distributed embedded sensing and control applications as a set of so-called spatio-temporal objects. Locality and continuity in the underlying physics of a problem domain give rise to spatially coherent and temporally contiguous objects in an appropriate metric space. Once parameterized by physical properties such as location, intensity (e.g., light, temperature, pressure), and motion (e.g., velocity), these objects can be aggregated and abstracted into more abstract descriptions. Applications are written as the creation and transformation of these abstract objects. We illustrate how these objects naturally arise from applications such as distributed sensing and actuation, and use an air-jet table system to demonstrate how such a physics-based encapsulation modularizes the design of sensing and control software. Unlike in traditional software design, where objects and operations are defined mathematically and possess a semantics independent of possible implementations, the objects in distributed embedded software are defined by the physics of the application, algorithmic considerations, and task requirements, as well as optimization criteria. The air-jet table example demonstrates that the grouping and abstraction of actuation devices are determined by laws of motion, the type of force allocation algorithms used, and the desired performance of the controller; this encapsulation greatly simplifies the design and implementation of a force allocation algorithm for the system and improves software modularity. Based on our practical experiences in designing several massively distributed sensing and actuation systems, we present a set of recommendations for distributed embedded software modeling and design.

In this paper, we advocate a general constraint-based control framework that is highly promising for building control systems with complex dynamic structures, such as modular self-reconfigurable robots. In this framework, a controller consists of constraint solving components distributed in a network of embedded processors. Constraint solvers are goal oriented deliberative agents that can be used as control regulators or as information retrievers. The framework is built on the attribute/service model (ASM), a middleware for coordinating actuators, sensors and tasks in distributed real-time embedded systems. The communications and coordination among the services are realized via shared attributes. Examples of controlling a modular self-reconfigurable robot are illustrated in the paper.