Interacting with team oriented plans in multi-robot systems

Team oriented plans have become a popular tool for operators to control teams of autonomous robots to pursue complex objectives in complex environments. Such plans allow an operator to specify high level directives and allow the team to autonomously determine how to implement such directives. However, the operators will often want to interrupt the activities of individual team members to deal with particular situations, such as a danger to a robot that the robot team cannot perceive. Previously, after such interrupts, the operator would usually need to restart the team plan to ensure its success. In this paper, we present an approach to encoding how interrupts can be smoothly handled within a team plan. Building on a team plan formalism that uses Colored Petri Nets, we describe a mechanism that allows a range of interrupts to be handled smoothly, allowing the team to efficiently continue with its task after the operator intervention. We validate the approach with an application of robotic watercraft and show improved overall efficiency. In particular, we consider a situation where several platforms should travel through a set of pre-specified locations, and we identify three specific cases that require the operator to interrupt the plan execution: (i) a boat must be pulled out; (ii) all boats should stop the plan and move to a pre-specified assembly position; (iii) a set of boats must synchronize to traverse a dangerous area one after the other. Our experiments show that the use of our interrupt mechanism decreases the time to complete the plan (up to 48 % reduction) and decreases the operator load (up to 80 % reduction in number of user actions). Moreover, we performed experiments with real robotic platforms to validate the applicability of our mechanism in the actual deployment of robotic watercraft.     

Inconsistent heuristics in theory and practice

In the field of heuristic search it is usually assumed that admissible heuristics are consistent, implying that consistency is a desirable attribute. The term “inconsistent heuristic” has, at times, been portrayed negatively, as something to be avoided. Part of this is historical: early research discovered that inconsistency can lead to poor performance for A^? (nodes might be re-expanded many times). However, the issue has never been fully investigated, and was not re-considered after the invention of IDA^?.This paper shows that many of the preconceived notions about inconsistent heuristics are outdated. The worst-case exponential time of inconsistent heuristics is shown to only occur on contrived graphs with edge weights that are exponential in the size of the graph. Furthermore, the paper shows that rather than being something to be avoided, inconsistent heuristics often add a diversity of heuristic values into a search which can lead to a reduction in the number of node expansions. Inconsistent heuristics are easy to create, contrary to the common perception in the AI literature. To demonstrate this, a number of methods for achieving effective inconsistent heuristics are presented.Pathmax is a way of propagating inconsistent heuristic values in the search from parent to children. This technique is generalized into bidirectional pathmax (BPMX) which propagates values from a parent to a child node, and vice versa. BPMX can be integrated into IDA^? and A^?. When inconsistent heuristics are used with BPMX, experimental results show a large reduction in the search effort required by IDA^?. Positive results are also presented for A^? searches.     

A Linear Variational System for Modelling From Curves

We present a linear system for modelling 3D surfaces from curves. Our system offers better performance, stability and precision in control than previous non‐linear systems. By exploring the direct relationship between a standard higher‐order Laplacian editing framework and Hermite spline curves, we introduce a new form of Cauchy constraint that makes our system easy to both implement and control. We introduce novel workflows that simplify the construction of 3D models from sketches. We show how to convert existing 3D meshes into our curve‐based representation for subsequent editing and modelling, allowing our technique to be applied to a wide range of existing 3D content.     

A practical approximation algorithm for the LMS line estimator

The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0<q?1. This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O(n²) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε_r?0, and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε_q?0. We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε_q>0 runs in O(nlogn) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm's expected running time is . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.     

Modeling expert problem solving in a game of chance: a Yahtzee© case study

Although developments on software agents have led to useful applications in automation of routine tasks such as electronic mail filtering, there is a scarcity of research that empirically evaluates the performance of a software agent versus that of a human reasoner, whose problem-solving capabilities the agent embodies. In the context of a game of a chance, namely Yahtzee©, we identified strategies deployed by expert human reasoners and developed a decision tree for agent development. This paper describes the computer implementation of the Yahtzee game as well as the software agent. It also presents a comparison of the performance of humans versus an automated agent. Results indicate that, in this context, the software agent embodies human expertise at a high level of fidelity.     

High-temperature superconducting microwave devices: Fundamental issues in materials, physics, and engineering

High-T _c superconductivity has generated a great deal of interest because of the challenges it presents in the fields of material science, condensed matter physics, and electrical engineering, and because of the potential applications which may result from these research efforts. Thin-film passive microwave components may become the first high-temperature superconducting (HTS) devices available for widespread use and commercialization. In this article, we review aspects of material science, physics, and engineering which directly impact high-T _c superconducting microwave devices and discuss issues which determine the performance of these devices. Methods of growing HTS thin films on large-area substrates, techniques for fabricating single-level HTS passive microwave components, and the relevant properties of high-T _c superconducting films are discussed, with a focus on thin films of the HTS material YBa₂Cu₃O_7–. Several known mechanisms for microwave loss in both the superconductor and the dielectric substrate are presented. An overview of the general classes of superconducting passive microwave devices is given, and representative microwave devices which have been recently demonstrated are described in detail. Examples of a select few HTS active microwave components are also presented. Potential microwave applications are illustrated with comparisons to current technology.     

Thermodynamics of iron-aluminum alloys at 1573 K

The activities of iron (Fe) and aluminum (Al) were measured in Fe-Al alloys at 1573 K using the ion-current-ratio technique in a high-temperature Knudsen cell mass spectrometer. The Fe-Al solutions exhibited negative deviations from ideality over the entire composition range. The activity coefficientsγ _Fe, andγ _A1 are given by the following equations as a function of mole fraction (x _Fe,x _Al): 1 $$\begin{gathered} 0< \chi _{A1}< 0.4 \hfill \\ ln \gamma _{Fe} = - 4.511 ( \pm 0.008)\chi _{A1}^2 \hfill \\ ln \gamma _{A1} = - 4.462 ( \pm 0.029)\chi _{Fe}^2 + 0.325( \pm 0.013) \hfill \\ 0.6< \chi _{A1}< 1.0 \hfill \\ ln \gamma _{Fe} = - 4.065 ( \pm 0.006)\chi _{A1}^2 + 0.099( \pm 0.003) \hfill \\ ln \gamma _{A1} = - 4.092 ( \pm 0.026)\chi _{Fe}^2 + 0.002( \pm 0.001) \hfill \\ \end{gathered} $$ The results showed good agreement with those obtained from previous investigations at other temperatures by extrapolation of the activity data to 1573 K.     

Automatic Design of Application Specific Instruction Set Extensions Through Dataflow Graph Exploration

General-purpose processors are often incapable of achieving the challenging cost, performance, and power demands of high-performance applications. To meet these demands, most systems employ a number of hardware accelerators to off-load the computationally demanding portions of the application. As an alternative to this strategy, we examine customizing the computation capabilities of a processor for a particular application. The processor is extended with hardware in the form of a set of custom function units and instruction set extensions. To effectively identify opportunities for creating custom hardware, a dataflow graph design space exploration engine heuristically identifies candidate computation subgraphs without artificially constraining their size or shape. The engine combines estimates of performance gain, cost, and inherent limitations of the processor to grow candidate graphs in profitable directions while pruning unprofitable paths. This paper describes the dataflow graph exploration engine and evaluates its effectiveness across a set of embedded applications.     

Stress transmission through three-dimensional granular crystals with stacking faults

We explore the effect of stacking fault defects on the transmission of forces in three-dimensional face-centered-cubic granular crystals. An external force is applied to a small area at the top surface of a crystalline packing of granular beads containing one or two stacking faults at various depths. The response forces at the bottom surface are measured and found to correspond to predictions based on vector force balance within the geometry of the defects. We identify the elementary stacking fault as a boundary between two pure face-centered-cubic crystals with different stacking orders. Other stacking faults produce response force patterns that can be viewed as resulting from repetitions of this basic defect. As the number of stacking faults increases, the intensity pattern evolves toward that of an hexagonal-close-packed crystal. This leads to the conclusion that the force pattern of that crystal structure can be viewed as the extreme limit of a face-centered-cubic crystal with a stacking fault at every layer.This work was supported by NSF-CTS 0090490 and by the NSF MRSEC Program under DMR-0213745. MJS acknowledges support by the University of Chicago MRSEC Summer 2002 REU program.