Complexity results on labeled shortest path problems from wireless routing metrics

Metrics to assess the cost of paths through networks are critical to ensuring the efficiency of network routing. This is particularly true in multi-radio multi-hop wireless networks. Effective metrics for these networks must measure the cost of a wireless path based not only on traditional measures such as throughput, but also on the distribution of wireless channels used. In this paper, we argue that routing metrics over such networks may be viewed as a class of existing shortest path problems, the formal language constrained path problems.On this basis, we describe labeled path problems corresponding to two multi-radio wireless routing metrics: Weighted Cumulative Expected Transmission Time (WCETT), developed by Draves et al., and Metric for Interference and Channel-switch (MIC), developed by Yang et al. For the first, we give a concise proof that calculating shortest WCETT paths is strongly NP-Complete for a variety of graph classes. We also show that the existing heuristic given by Draves et al. is an approximator. For the second, we show that calculating loop-free (simple) shortest MIC paths is NP-Complete, and additionally show that the optimization version of the problem is NPO PB-Complete. This result implies that shortest simple MIC paths are only poorly approximable in the worst case.Furthermore, we demonstrate how the polynomial-time algorithm for shortest MIC paths is derivable from an existing language constrained shortest path algorithm. We use this as a basis to exhibit the general utility of viewing multi-channel wireless routing metrics as labeled graph problems, and discuss how a class of related polynomial-time computable metrics are derivable from this algorithm.     

Mobility profiler: A framework for discovering mobility profiles of cell phone users

Mobility path information of cell phone users play a crucial role in a wide range of cell phone applications, including context based search and advertising, early warning systems, city-wide sensing applications such as air pollution exposure estimation and traffic planning. However, there is a disconnect between the low level location data logs available from the cell phones and the high level mobility path information required to support these cell phone applications. In this paper, we present formal definitions to capture the cell phone users’ mobility patterns and profiles, and provide a complete framework, Mobility Profiler, for discovering mobile cell phone user profiles starting from cell based location data. We use real-world cell phone log data (of over 350 K h of coverage) to demonstrate our framework and perform experiments for discovering frequent mobility patterns and profiles. Our analysis of mobility profiles of cell phone users expose a significant long tail in a user’s location-time distribution: A total of 15% of a cell phone user’s time is spent on average in locations that each appears with less than 1% of total time.     

The feasibility of general task systems with precedence constraints on multiprocessor platforms

Feasibility analysis determines (prior to system execution-time) whether a specified collection of hard-real-time jobs executed on a processing platform can meet all deadlines. In this paper, we derive near-optimal sufficient tests for determining whether a given collection of jobs can feasibly meet all deadlines upon a specified multiprocessor platform assuming job migration is permitted. The collection of jobs may contain precedence constraints upon the order of execution of these jobs. The derived tests are general enough to be applied even when the collection of jobs is incompletely specified. We discuss the applicability of these tests to the scheduling of collections of jobs that are generated by systems of recurrent real-time tasks. We also show that our feasibility conditions may be used to obtain global-EDF schedulability conditions.

Situation awareness acquired from monitoring process plants – the Process Overview concept and measure

We introduce Process Overview, a situation awareness characterisation of the knowledge derived from monitoring process plants. Process Overview is based on observational studies of process control work in the literature. The characterisation is applied to develop a query-based measure called the Process Overview Measure. The goal of the measure is to improve coupling between situation and awareness according to process plant properties and operator cognitive work. A companion article presents the empirical evaluation of the Process Overview Measure in a realistic process control setting. The Process Overview Measure demonstrated sensitivity and validity by revealing significant effects of experimental manipulations that corroborated with other empirical results. The measure also demonstrated adequate inter-rater reliability and practicality for measuring SA based on data collected by process experts.

Practitioner Summary: The Process Overview Measure is a query-based measure for assessing operator situation awareness from monitoring process plants in representative settings.     

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.