There is now a large body of techniques, many based on formal methods, for describing and realizing complex robotics tasks, including those involving a variety of rich goals and time-extended behavior. This paper explores the limits of what sorts of tasks are specifiable, examining how the precise grounding of specifications -that is, whether the specification is given in terms of the robot's states, its actions and observations, its knowledge, or some other information-is crucial to whether a given task can be specified. While prior work included some description of particular choices for this grounding, our contribution treats this aspect as a first-class citizen: we introduce notation to deal with a large class of problems, and examine how the grounding affects what tasks can be posed. The results demonstrate that certain classes of tasks are specifiable under different combinations of groundings.

This paper contemplates the possibility of asking robots questions and having them use their ability to go out into the environment and probe it, in combination with what they already know of the world, to provide answers. We describe a method whereby a robot system efficiently answers such questions on the basis of reasoning about observations as they are made, interrelationships between multiple pieces of evidence, and what they imply.A central idea in the approach is to maintain a separation of concerns so that managing ‘what is known’ is decoupled from ‘how it is learned’. This idea is realized in a graph-based representation well-suited to algorithmic manipulation and composition, exposing synergies rife for optimization. We show how to use this representation to leverage both informational overlap between multiple simultaneous queries and availability of multiple robots working in concert to answer those queries. We demonstrate these ideas in a simple case study and present data illustrating how plan quality (in terms of cost to execute) can be improved through an optimization operation that is robot agnostic.

Future conceptions of agile, just-in-time fabrication, lean and “smart” manufacturing, and a host of allied processes that exploit advanced automation, depend in part on realizing improvements in logistics planning. The present paper hypothesizes that the key to improving flexibility will be the inclusion of sophisticated, time-correlated stochastic models of demand—whether that be demand by end-user consumers directly, or by other down-stream processes. Such dynamic models of demand, unfortunately, can greatly increase the space in which planning occurs when treated, as is common for planning under uncertainty, via the Markov Decision Processes formulation. To tackle this challenge, we identify three aspects that we postulate appear as commonalities in many logistics settings. They lead to an approach for approximate reduction of the planning problem via causal decoupling, which gives a spectrum of solutions where weakening time correlations affords faster optimization. Empirical results on small case studies —in lean manufacturing and commodity routing—show that retaining some limited (but non-zero) amount of temporal structure can provide a useful compromise between quality of the solution obtained and computation required.

We consider a robot that answers questions about its environment by traveling to appropriate places and then sensing. Questions are posed as structured queries and may involve conditional or contingent relationships between observable properties. After formulating this problem, and empha-sizing the advantages of exploiting deducible information, we describe how non-trivial knowledge of the world and queries can be given a convenient, concise, unified representation via reduced ordered binary decision diagrams (BDDs). To use these data structures directly for inference and planning, we introduce a new product operation, and generalize the classic dynamic variable reordering techniques to solve planning problems. Also, finally, we evaluate optimizations that exploit locality.

State minimization of combinatorial filters is a fundamental problem that arises, for example, in building cheap, resource-efficient robots. But exact minimization is known to be NP-hard. This paper conducts a more nuanced analysis of this hardness than up till now, and uncovers two factors which contribute to this complexity. We show each factor is a distinct source of the problem's hardness and are able, thereby, to shed some light on the role played by (1) structure of the graph that encodes compatibility relationships, and (2) determinism-enforcing constraints. Just as a line of prior work has sought to introduce additional assumptions and identify sub-classes that lead to practical state reduction, we next use this new, sharper understanding to explore special cases for which exact minimization is efficient. We introduce a new algorithm for constraint repair that applies to a large sub-class of filters, subsuming three distinct special cases for which the possibility of optimal minimization in polynomial time was known earlier. While the efficiency in each of these three cases previously appeared to stem from seemingly dissimilar properties, when seen through the lens of the present work, their commonality now becomes clear. We also provide entirely new families of filters that are efficiently reducible.

It is easier to program effective robots when they inhabit highly structured environments. The growing literature on methods to aid robot design has given comparatively little consideration to elements external to the robot itself, yet such elements can encode or enhance information (to improve perception), can alter the effects or costs of actions (to help control), and can provide regularity by imposing constraints. External elements have the potential to be shared, to scale elastically, and to spread both benefits and installation/operating costs. These are traits of infrastructure in support of robots. We introduce a basic but flexible mathematical model –via the MDP framework– for rational evaluation of proposed additions and changes to environments, including where infrastructure may improve precision or performance of either perception or actuation. Through it, one can assess the numbers of agents needed for infrastructure investment to be economical, determine when installation costs would be recouped, and evaluate the effect of behavior changes as responses to environmental modifications. To demonstrate how the model can be instantiated, four simple but practical case studies are presented.

A useful capability is that of classifying some agent's behavior using data from a sequence, or trace, of sensor measurements. The sensor selection problem involves choosing a subset of available sensors to ensure that, when generated, observation traces will contain enough information to determine whether the agent's activities match some pattern. In generalizing prior work, this paper studies a formulation in which multiple behavioral itineraries may be supplied, with sensors selected to distinguish between behaviors. This allows one to pose fine-grained questions, e.g., to position the agent's activity on a spectrum. In addition, with multiple itineraries, one can also ask about choices of sensors where some behavior is always plausibly concealed by (or mistaken for) another. Using sensor ambiguity to limit the acquisition of knowledge is a strong privacy guarantee, a form of guarantee which some earlier work examined under formulations distinct from our inter-itinerary conflation approach. By concretely formulating privacy requirements for sensor selection, this paper connects both lines of work in a novel fashion: privacy-where there is a bound from above, and behavior verification-where sensors choices are bounded from below. We examine the worst-case computational complexity that results from both types of bounds, proving that upper bounds are more challenging under standard computational complexity assumptions. The problem is intractable in general, but we introduce an approach to solving this problem that can exploit interrelationships between constraints, and identify opportunities for optimizations. Case studies are presented to demonstrate the usefulness and scalability of our proposed solution, and to assess the impact of the optimizations.

A useful capability is that of classifying some agent's behavior using data from a sequence, or trace, of sensor measurements. The sensor selection problem involves choosing a subset of available sensors to ensure that, when generated, observation traces will contain enough information to determine whether the agent's activities match some pattern. In generalizing prior work, this paper studies a formulation in which multiple behavioral itineraries may be supplied, with sensors selected to distinguish between behaviors. This allows one to pose fine-grained questions, e.g., to position the agent's activity on a spectrum. In addition, with multiple itineraries, one can also ask about choices of sensors where some behavior is always plausibly concealed by (or mistaken for) another. Using sensor ambiguity to limit the acquisition of knowledge is a strong privacy guarantee, a form of guarantee which some earlier work examined under formulations distinct from our inter-itinerary conflation approach. By concretely formulating privacy requirements for sensor selection, this paper connects both lines of work in a novel fashion: privacy-where there is a bound from above, and behavior verification-where sensors choices are bounded from below. We examine the worst-case computational complexity that results from both types of bounds, proving that upper bounds are more challenging under standard computational complexity assumptions. The problem is intractable in general, but we introduce an approach to solving this problem that can exploit interrelationships between constraints, and identify opportunities for optimizations. Case studies are presented to demonstrate the usefulness and scalability of our proposed solution, and to assess the impact of the optimizations.

The problem of combinatorial filter reduction arises from resource optimization in robots; it is one specific way in which automation can help to achieve minimalism, to build better robots. This paper contributes a new definition of filter minimization that is broader than its antecedents, allowing filters (input, output, or both) to be nondeterministic. This changes the problem considerably. Nondeterministic filters may re-use states to obtain more ‘behavior’ per vertex. We show that the gap in size can be significant (larger than polyno-mial), suggesting such cases will generally be more challenging than deterministic problems. Indeed, this is supported by the core complexity result established in this paper: producing nondeterministic minimizers is PSPACE-hard. The hardness separation for minimization existing between deterministic filter and automata, thus, fails to hold for the nondeterministic case.

Practical robot designs must strike a compromise between fabrication/manufacture cost and anticipated execution performance. Compared to parsimonious designs, more capable (and hence more expensive) robots generally achieve their ends with greater efficiency. This paper examines how the roboticist might explore the space of designs to gain an understanding of such trade-offs. We focus, specifically, on design choices that alter the set of actions available to the robot, and model those actions as involving uncertainty. We consider planning problems under the Markov Decision Process (MDP) model, which leads us to examine how to relate the cost of some design to the expected cost of an execution for the optimal policies feasible with that design. The complexity of this problem ─expressed via hardness in the fixed parameter tractability sense─depends on the number of actions to choose from. When that number is not negligible, we give a novel representation and an algorithm utilizing that structure that allows useful savings over naïve enumeration.

We study planning problems faced by robots operating in uncertain environments with incomplete knowledge of state, and actions that are noisy and/or imprecise. This paper identifies a new problem sub-class that models settings in which information is revealed only intermittently through some exogenous process that provides state information periodically. Several practical domains fit this model, including the specific scenario that motivates our research: autonomous navigation of a planetary exploration rover augmented by remote imaging. With an eye to efficient specialized solution methods, we examine the structure of instances of this sub-class. They lead to Markov Decision Processes with exponentially large action-spaces but for which, as those actions comprise sequences of more atomic elements, one may establish performance bounds by comparing policies under different information assumptions. This provides a way in which to construct performance bounds systematically. Such bounds are useful because, in conjunction with the insights they confer, they can be employed in bounding-based methods to obtain high-quality solutions efficiently; the empirical results we present demonstrate their effectiveness for the considered problems. The foregoing has also alluded to the distinctive role that time plays for these problems -more specifically: time until information is revealed- and we uncover and discuss several interesting subtleties in this regard.

Reduction of combinatorial filters involves compressing state representations that robots use. Such optimization arises in automating the construction of minimalist robots. But exact combinatorial filter reduction is an NP-complete problem and all current techniques are either inexact or formalized with exponentially many constraints. This paper proposes a new formalization needing only a polynomial number of constraints, and characterizes these constraints in three different forms: nonlinear, linear, and conjunctive normal form. Empirical results show that constraints in conjunctive normal form capture the problem most effectively, leading to a method that outperforms the others. Further examination indicates that a substantial proportion of constraints remain inactive during iterative filter reduction. To leverage this observation, we introduce just-in-time generation of such constraints, which yields improvements in efficiency and has the potential to minimize large filters.

We consider a robot tasked with observing its environment and later selectively summarizing what it saw as a vivid, structured narrative. The robot interacts with an uncertain environment, modelled as a stochastic process, and must decide what events to pay attention to (substance), and how to best make its recording (style) for later compilation of its summary. If carrying a video camera, for example, it must decide where to be, what to aim the camera at, and which stylistic selections, like the focus and level of zoom, are most suitable. This paper examines planning algorithms that help the robot predict events that (1)will likely occur; (2)would be useful in telling a tale; and (3)may be hewed to cohere stylistically. The third factor, a time-extended requirement, is entirely neglected in earlier, simpler work. With formulations based on underlying Markov Decision Processes, we compare two algorithms: a monolithic planner that jointly plans over events and style pairs and a decoupled approach that prescribes style conditioned on events. The decoupled approach is seen to be effective and much faster to compute, suggesting that computational expediency justifies the separation of substance from style. Finally, we also report on our hardware implementation.

Suppose an agent asserts that it will move through an environment in some way. When the agent executes its motion, how does one verify the claim? The problem arises in a range of contexts including validating safety claims about robot behavior, applications in security and surveillance, and for both the conception and the (physical) design and logistics of scientific experiments. Given a set of feasible sensors to select from, we ask how to choose sensors optimally in order to ensure that the agent’s execution does indeed fit its pre-disclosed itinerary. Our treatment is distinguished from prior work in sensor selection by two aspects: the form the itinerary takes (a regular language of transitions) and that families of sensor choices can be grouped as a single choice. Both are intimately tied together, permitting construction of a product automaton because the same physical sensors (i.e., the same choice) can appear multiple times. This paper establishes the hardness of sensor selection for itinerary validation within this treatment, and proposes an exact algorithm based on an integer linear programming (ILP) formulation that is capable of solving problem instances of moderate size. We demonstrate its efficacy on small-scale case studies, including one motivated by wildlife tracking.

This article examines the selection of a robot’s actuation and sensing hardware to minimize the cost of that design while ensuring that the robot is capable of carrying out a plan to complete a task. Its primary contribution is in the study of the hardness of reasonable formal models for that minimization problem. Specifically, for the case in which sensing hardware is held fixed, we show that this algorithmic design problem is NP-hard even for particularly simple classes of cost functions, confirming what many perhaps have suspected about this sort of design-time optimization. We also introduce a formalism, based on the notion of label maps, for the broader problem in which the design space encompasses choices for both actuation and sensing components. As a result, for several questions of interest, having both optimality and efficiency of solution is unlikely. However, we also show that, for some specific types of cost functions, the problem is either polynomial-time solvable or fixed-parameter tractable.Note to Practitioners—Despite the primary results being theoretical and, further, taking the form of bad news, this article still has considerable value to practitioners. Specifically, assuming that one has been employing heuristic or approximate solutions to robot design problems, this article serves as a justification for doing so. Moreover, it delineates some circumstances in which one can, in a sense, do better and achieve genuine optima with practical algorithms.

This article presents and studies a recursive information consensus filter for decentralized dynamic state estimation under circumstances in which the communication network is unreliable. Local estimators are assumed to have access only to local information, and no structure is assumed about the topology of the communication network, which need not be connected at all times. The filter is a hybrid approach: it uses iterative covariance intersection to reach consensus over priors, which might become correlated, while consensus over new information is handled using weights based on a Metropolis–Hastings Markov chain. We establish bounds for estimation performance and show that this hybrid method produces unbiased conservative estimates that are better than covariance intersection. The performance of the hybrid method is evaluated extensively, including comparisons with competing algorithms, with a hypothetical “full history” yardstick, and centralized performance. We conduct an assessment on a realistic atmospheric dispersion problem and also on more carefully crafted settings to help characterize particular aspects of the performance.

This paper proposes a new loss function for linear autoencoders (LAEs) and analytically identifies the structure of the associated loss surface. Optimizing the conventional Mean Square Error (MSE) loss results in a decoder matrix that spans the principal subspace of the sample covariance of the data, but, owing to an invariance that cancels out in the global map, it will fail to identify the exact eigenvectors. We show here that our proposed loss function eliminates this issue, so the decoder converges to the exact ordered unnormalized eigenvectors of the sample covariance matrix. We characterize the full structure of the new loss landscape by establishing an analytical expression for the set of all critical points, showing that it is a subset of critical points of MSE, and that all local minima are still global. Specifically, the invariant global minima under MSE are shown to become saddle points under the new loss. Additionally, the computational complexity of the loss and its gradients are the same as MSE and, thus, the new loss is not only of theoretical importance but is of practical value, e.g., for low-rank approximation.

Whether a robot can perform some specific task depends on several aspects, including the robot's sensors and the plans it possesses. We are interested in search algorithms that treat plans and sensor designs jointly, yielding solutions-i.e., plan and sensor characterization pairs-if and only if they exist. Such algorithms can help roboticists explore the space of sensors to aid in making design trade-offs. Generalizing prior work where sensors are modeled abstractly as sensor maps on p-graphs, the present paper increases the potential sensors which can be sought significantly. But doing so enlarges a problem currently on the outer limits of being considered tractable. Toward taming this complexity, two contributions are made: (1) we show how to represent the search space for this more general problem and describe data structures that enable whole sets of sensors to be summarized via a single special representative; (2) we give a means by which other structure (either task domain knowledge, sensor technology or fabrication constraints) can be incorporated to reduce the sets to be enumerated. These lead to algorithms that we have implemented and which suffice to solve particular problem instances, albeit only of small scale. Nevertheless, the algorithm aids in helping understand what attributes sensors must possess and what information they must provide in order to ensure a robot can achieve its goals despite non-determinism.

We consider problems in which robots conspire to present a view of the world that differs from reality. The inquiry is motivated by the problem of validating robot behavior physically despite there being a discrepancy between the robots we have at hand and those we wish to study, or the environment for testing that is available versus that which is desired, or other potential mismatches in this vein. After formulating the concept of a convincing illusion, essentially a notion of system simulation that takes place in the real world, we examine the implications of this type of simulability in terms of infrastructure requirements. Time is one important resource: some robots may be able to simulate some others but, perhaps, only at a rate that is slower than real-time. This difference gives a way of relating the simulating and the simulated systems in a form that is relative. We establish some theorems, including one with the flavor of an impossibility result, and providing several examples throughout. Finally, we present data from a simple multi-robot experiment based on this theory, with a robot navigating amid an unbounded field of obstacles."Truth is beautiful, without doubt; but so are lies."-Ralph Waldo Emerson.

Drivers and other road users often encounter situations (e.g., arriving at an intersection simultaneously) where priority is ambiguous or unclear but must be resolved via communication to reach agreement. This poses a challenge for autonomous vehicles, for which no direct means for expressing intent and acknowledgment has yet been established. This paper contributes a minimal model to manage ambiguity and produce actions that are expressive and encode aspects of intent. Specifically, intent is treated as a latent variable, communicated implicitly through a partially observable Markov decision process (POMDP). We validate the model in a simple setting: a simulation of a prototypical crossing with a vehicle and one pedestrian at an unsignalized intersection. We further report use of our self-driving Ford Lincoln MKZ platform, through which we conducted experimental trials of the method involving real-time interaction. The experiment shows the method achieves safe and efficient navigation.

In this article, we study multirobot task allocation problems where task costs vary. The variation may be, for example, due to the revelation of new information or other dynamic circumstances. As robots update their cost estimates, typically they will update task assignments to reflect the new information using additional communication and computation. In dynamic settings, the robots are continually repairing the optimality of the system's task assignments, which can incur substantial communication and computation. We investigate how one can reduce communication and centralized computation expense during execution by using a prior model of how costs may change and performing upfront computation of possible robot-task assignments. First, we develop an algorithm that partitions a team of robots into several independent subteams that are able to maintain global optimality by communicating entirely amongst themselves. Second, we propose a method for computing the worst-case cost suboptimality if robots persist with the initial assignment and perform no further communication and computation. Finally, we introduce an algorithm to assess whether cost changes affect the optimality of the current assignment through a succession of local communication exchanges. Experimental results show that the proposed methods are helpful in reducing the degree of centralization needed by a multirobot system (e.g., the third method gave at least 45% reduction of global communication across all scenarios studied). The methods are valuable in transitioning multirobot techniques, which have met with success in structured applications (such as factories and warehouses) to the broader, wilder world.

We consider the problem of multiple robots that must cooperate within a shared environment, but which wish to limit the information they disclose during their coordination efforts. Specifically, we examine the problems of privacy-preserving rendezvous and persistent monitoring. In the former, the robots construct a joint plan to have them meet, without either knowing beforehand where or when the meeting will occur. In the latter, multiple robots dynamically cover a region of space-they plan collective motions which are collision-free but with the assurance that agents remain ignorant of the paths of others. Accordingly, the tasks are sort of inverses in that the robots must collectively determine whether their joint paths collide or not, then, using this, achieve their collective task. Other than what is learned by the outcome of the joint-collision determination, the robots possess no details of the other paths. Our approach builds on garbled circuits and homomorphic encryption to realize basic secure path intersection primitives. We present algorithms, a software implementation, and a physical experiment on mobile robots to test the practical feasibility of our approach. We believe that these ideas provide a valuable direction for adoption in small Unmanned Systems belonging to different stakeholders.

This paper addresses the problem of using autonomous robots to record events that obey narrative structure. The work is motivated by a vision of robot teams that can, for example, produce individualized highlight videos for each runner in a large-scale road race such as a marathon. We introduce a method for specifying the desired structure as a function that describes how well the captured events can be used to produce an output that meets the specification. This function is specified in a compact, legible form similar to a weighted finite automaton. Then we describe a planner that uses simple predictions of future events to coordinate the robots' efforts to capture the most important events, as determined by the specification. We describe an implementation of this approach, and demonstrate its effectiveness in a simulated race scenario both in simulation and in a hardware testbed.

In robot swarms operating under highly restrictive sensing and communication constraints, individuals may need to use direct physical proximity to facilitate information exchange. However, in certain task-related scenarios, this requirement might conflict with the need for robots to spread out in the environment, e.g., for distributed sensing or surveillance applications. This paper demonstrates how a swarm of minimally-equipped robots can form high-density robot aggregates that coexist with lower robot densities in space. We envision a scenario where a swarm of vibration-driven robots-which sit atop bristles and achieve directed motion by vibrating them-move randomly in an environment while colliding with each other. Theoretical techniques from the study of far-from-equilibrium collectives and statistical mechanics clarify the mechanisms underlying the formation of these high and low density regions. Specifically, we capitalize on a transformation that connects the collective properties of a system of self-propelled particles with that of a well-studied molecular fluid system, thereby inheriting the rich theory of equilibrium thermodynamics. Real robot experiments as well as simulations illustrate how inter-robot collisions can precipitate the formation of non-uniform robot densities in a closed and bounded region.

Motivated by the need for tools to aid in the design of effective robots, we examine how to determine the role that particular sensing and actuator resources play in enabling a robot to achieve useful ends. Rather than merely asking “will this sensor suffice?” we classify general modifications to the set of sensors and actuators based on the feasibility of accomplishing given tasks using these sets. The goal is to probe the boundary between modifications that are destructive on a given planning problem, and modifications that are not. Since this boundary itself can be impractically large, classic search methods are of no avail to summarize discriminatory features on this boundary. Instead, we propose a decision tree learning method to efficiently construct a compact implicit representation of the boundary. The idea is to allow the designer to use prior knowledge to constrain the search, then use the tool to probe the boundary subject to those constraints, gaining insight into the information necessary for a robot to ensure task achievement. Ultimately we envision a interactive process where additional constraints are repeatedly included as new light is shed. We aim to pave the way for interactive tools that help the roboticist navigate the complexities of the design space. We describe an implementation of this approach along with experimental results that show that the method can construct decision trees with explanatory value. Our experiments suggest that some domain knowledge (specifically picking features that emphasize monotonicity) substantially improves running-time with only negligible reduction in accuracy.

Though autonomous vehicles are currently operating in several places, many important questions within the field of autonomous vehicle research remain to be addressed satisfactorily. In this paper, we examine the role of communication between pedestrians and autonomous vehicles at unsignalized intersections. The nature of interaction between pedestrians and autonomous vehicles remains mostly in the realm of speculation currently. Of course, pedestrian's reactions towards autonomous vehicles will gradually change over time owing to habituation, but it is clear that this topic requires urgent and ongoing study, not least of all because engineers require some working model for pedestrian- autonomous-vehicle communication. Our paper proposes a decision-theoretic model that expresses the interaction between a pedestrian and a vehicle. The model considers the interaction between a pedestrian and a vehicle as expressed an MDP, based on prior work conducted by psychologists examining similar experimental conditions. We describe this model and our simulation study of behavior it exhibits. The preliminary results on evaluating the behavior of the autonomous vehicle are promising and we believe it can help reduce the data needed to develop fuller models.

Marine robots and unmanned surface vehicles will increasingly be deployed in rivers and riverine environments. The structure produced by flowing waters may be exploited for purposes of estimation, planning, and control. This paper adopts a widely acknowledged model for the geometry of watercourse channels, namely sine-generated curves, as a basis for estimators that predict the shape of the yet unseen portion of the river. Predictions of this sort help a robot anticipate the future, for example, in throttling speeds as it rounds a bend. After examining how to reparameterize standard filters to incorporate this model, we compare the performance of three Gaussian filters and show that nonideality and theoretical challenges (of non-linearity, multi-modality/periodicity) degrade the performance of standard Kalman filters severely, but can be successfully mitigated by imposing an interval constraint. Thereafter, we present results of a constrained interval Kalman filter on data from three natural rivers. The results we report show the effectiveness of our method on the estimation of meander parameters. The results we report, including data from simulation, from maps, and from GPS tracks of a boat on the Colorado river, show the effectiveness of our method on the estimation of meander parameters.

We wish to minimize the information that a robot maintains to carry out its task. Filters are one way to keep stored state consistent with sensed values, though they may also capture some information about the structure of the world that the robot inhabits. This paper builds on prior work on (improper) filter minimization, but considers a new way to characterize structure in the world. By introducing a probabilistic model, one can define a notion of expected distance between two filters. Then, with such a measure, we pose the question of optimal lossy compression in the sense of having minimal expected distance. The problem retains the NP-hardness of the non-probabilistic worst-case minimization and, consequently, in this paper we focus on developing an effective heuristic algorithm. Our results illustrate that, in settings where the probabilities describe evolution of the world's state, the algorithm can do substantially better than existing worst-case minimization techniques oblivious to such structure.

Motivated by circumstances with severe computational resource limits (e.g., settings with strong constraints on memory or communication), this paper addresses the problem of concisely representing and processing information for estimation and planning tasks. In this paper, conciseness is a measure of explicit representational complexity: for filtering, we are concerned with maintaining as little state as possible to perform a given task; for the planning case, we wish to generate the plan graph (or policy graph) with the fewest vertices that is correct and also complete. We present hardness results showing that both filtering and planning are NP-hard to perform in an optimally concise way, and that the related decision problems are NP-complete. We also describe algorithms for filter reduction and concise planning, for which these hardness results justify the potentially suboptimal output. The filter-reduction algorithm accepts as input an arbitrary combinatorial filter, expressed as a transition graph, and outputs an equivalent filter that uses fewer I-states to complete the same filtering task. The planning algorithm, using the filter-reduction algorithm as a subroutine, generates concise plans for planning problems that may involve both nondeterminism and partial observability. Both algorithms are governed by parameters that encode tradeoffs between computational efficiency and solution quality. We describe implementation of both algorithms and present a series of experiments evaluating their effectiveness.Note to Practitioners—The reduced filters and plans explored in this paper are of practical interest in several contexts, including: 1) on robot platforms with severely limited computational power; 2) communication over low-bandwidth noisy channels; 3) a special instance of the previous case includes human-robot interaction settings where interfaces constrain information transfer; and 4) understanding the size and the structure of concise plans or filters for given problems provides insights into those problems (e.g., to assess the value of a particular sensor by comparing the size of filters with or without it.)

There are several practical reasons to endow a mobile robot with a tether, but doing so adds considerable complexity to the problem of moving the robot. The feasibility of a particular motion in such systems depends on topological constraints imposed by the interplay of the robot's tether and its environment. The physical properties of the tether may also rule out configurations that would be possible otherwise. Little work has addressed these latter constraints, despite the considerable interest in motion planning for tethered robots recently. We examine the problem of planning motions of a planar robot connected via a cable of limited length to a fixed point in ℝ2 when the tether has a constraint on its curvature, which adds appreciably to the realism of the cable model over existing work. We incorporate Dubins's theory of curves with work on planning with topological constraints to concisely represent the configuration space manifold, leading to an atlas of the manifold consisting of locally continuous charts that represent the cable's curvature limits conveniently. Any configuration of the tether and the robot is described in our representation with two elements: (1) a discrete structure that characterizes the cable's position and (2) an element within a single continuous chart. We provide an algorithm that explores the necessary parts of this atlas on-the-fly to locate paths efficiently.

This paper presents a new recursive information consensus filter for decentralized dynamic-state estimation. Local estimators are assumed to have access only to local information and no structure is assumed about the topology of the communication network, which need not be connected at all times. Iterative Covariance Intersection (ICI) is used to reach consensus over priors which might become correlated, while consensus over new information is handled using weights based on a Metropolis Hastings Markov Chain (MHMC). We establish bounds for estimation performance and show that our method produces unbiased conservative estimates that are better than CI. The performance of the proposed method is evaluated and compared with competing algorithms on an atmospheric dispersion problem.

This paper describes an end-to-end learning framework that allows a novice to create a model from data easily by helping structure the model building process and capturing extended aspects of domain knowledge. By treating the whole modeling process interactively and exploiting high-level knowledge in the form of an ontology, the framework is able to aid the user in a number of ways, including in helping to avoid pitfalls such as data dredging. Prudence must be exercised to avoid these hazards: certain conclusions may be supported by extra knowledge if, for example, there are reasons to trust a particular narrower set of hypotheses. This paper adopts the solution of using higher-level knowledge in order to allow this sort of domain knowledge to be inferred automatically, thereby selecting only relevant input attributes and thence constraining the hypothesis space. We describe how the framework automatically exploits structured knowledge in an ontology to identify relevant concepts, and how a data extraction component can make use of online data sources to find measurements of those concepts so that their relevance can be evaluated. To validate our approach, models of four different problem domains were built using our implementation of the framework. Prediction error on unseen examples of these models show that our framework, making use of the ontology, helps to improve model generalization.

For self-organized multi-robot systems, one of the widely studied task domains is object clustering, which involves gathering randomly scattered objects into a few piles. Earlier studies have pointed out that environmental boundaries influence the cluster formation process, generally causing clusters to form around the perimeter rather than centrally within the workspace. But it is usually central clusters that are desired in robotic clustering systems. In this paper, we derive general conditions that prevent the problem of boundaries causing perimeter clusters. We develop a mathematical model to explain how sets of clusters evolve into a single cluster without any boundary cluster being formed. Through analysis of the model, we show that time-averaged spatial densities of the robots play a significant role in producing conditions that ensure a single central cluster emerges. Thus, local densities of robots can be considered a system-level control parameter to achieve this task. We further investigate how the physical packing of clusters affects clustering dynamics. To do this, we introduce a measure of scaled compactness and show that the lifetime of clusters is well predicted by this descriptor.

We address the problem of finding the optimal assignment of tasks to a team of robots when the associated costs may vary, which arises when robots deal with uncertain or dynamic situations. We detail how to compute a sensitivity analysis that characterizes how much costs may change before optimality is violated. Using this analysis, robots are able to avoid unnecessary re-assignment computations and reduce global communication. First, given a model of how costs may evolve, we develop an algorithm to partition the robots into independent cliques, each of which maintains global optimality by communicating only amongst themselves. Second, we propose a method for computing the worst-case sub-optimality if robots persist with the initial assignment, performing no further communication/computation. Lastly, we develop an algorithm that assesses whether cost changes affect the optimality through an escalating succession of local checks. Experiments show that the methods reduce the degree of centralization needed by a multi-robot system.

We address the problem of deciding what information a robot should transmit to the outside world, by exploring a setting where some information (e.g., current status of the task) must be shared in order for the robot to be useful, but where, simultaneously, we wish to impose limits which ensure certain information is never divulged. These sorts of conditions arise in several circumstances of increasing relevance: robots that can provide some guarantee of privacy to their users, controllers which safely use untrusted “cloud” services or smart-space infrastructure, or robots that act as inspection devices in information-sensitive contexts (e.g., factories, nuclear plants, etc.) We introduce an algorithm which takes as input an arbitrary combinatorial filter, expressed as a transition graph, and a set of constraints, constituting both upper and lower bounds, that specify the desired informational properties. The algorithm produces a coarser version of the input filter which possesses the desired informational properties, if and only if such a filter exists. We show that determining whether it is possible to satisfy both the distinguishablity and indistinguishablity constraints is NP-hard. The hardness result helps justify the worst-case running time of the algorithm. We describe an implementation of the algorithm along with empirical results showing that, beyond some minimum problem complexity, the algorithm is faster than naïve filter enumeration, albeit with greater memory requirements.

This paper considers multirobot task allocation problems where the estimated costs for performing tasks are interrelated, and the overall team objective need not be a standard sum-of-costs (or utilities) model, enabling straightforward treatment of the additional costs incurred by resource contention. In the model we introduce, a team may choose one of a set of shared resources to perform a task (e.g., several routes to reach a destination), and interference is modeled when multiple robots use the same resource. We show that the general problem is NP-hard, and investigate specialized subinstances with particular cost structures. For the general problem, we describe an exact algorithm which finds an optimal assignment in a reasonable time on small instances. Aiming at larger problems, we turn two particular subinstances, introducing an two algorithms that find assignments quickly even for problems of considerable size, the first being optimal, the second being an approximation algorithm but also producing high-quality solutions with bounded suboptimality.

It can be useful for a robot in a team to recruit the help of others after considering their poses in space. When the initiating robot is aware of the network addresses (or IDs) of the robots it may ask for cooperation over the network. But if the initiating robot is ignorant of their IDs then it becomes rather more complex or time consuming. In this paper, robots use a simple visual (locally sensed) gesture (such as a light being turned on or off) in addition to wireless messages to quickly and effectively establish a one-to-one association between physical location IDs and wireless IDs. This paper identifies, describes, formalizes, and then generalizes the problem of establishing a local association between neighboring robots’ physical location IDs (in the reference frame of an observing robot) and their wireless IDs. We describe three algorithms that solve this problem: two are deterministic algorithms and one is a probabilistic algorithm. Using the algorithms and formalism, we examine the structure underlying this association problem.

Environmental monitoring, an important application for robots, has begun to be addressed recently with linear least squares regression techniques because they estimate the values of measured attributes and their uncertainty. But several challenges remain when performing adaptive sampling in a communication-constrained distributed multi-robot setting. When the attributes of interest evolve over time (as is natural for many environments) any non-homogeneous spatial variability may necessitate continual re-modeling of the field dynamics and/or re-sampling of the field. This raises questions about the robots' division of labor and workload balance that can be difficult to address when sample information is not stored centrally. This paper tackles these coordination problems efficiently by introducing a sub-division-based modeling technique appropriate for distributed decision-making. We augment Ordinary Kriging to enable representation of a field's (potentially non-homogeneous) evolution through Bayes filtering that characterize the underlying dynamics. This approach not only enables adaptive path planning in the field, but the sub-divided areas lead to a straightforward formulation of the optimal workload distribution through modification of an approximate graph partitioning algorithm. Using a simulated multi-robot sampling scenario, we demonstrate and validate the approach. The experiments show good performance in terms of cross-validation using real values and illustrate how hotspots are identified and modeled, in turn affecting the division of labor.

We consider optimization of the multi-robot task-allocation problem when the overall performance of the team need not be a standard sum-of-cost model. We introduce a generalization that allows for the additional cost incurred by resource contention to be treated in a straightforward manner. In this variant, robots may choose one of shared resources to perform a task, and interference may be modeled as occurring when multiple robots use the same resource. We investigate the general NP-hard problem and instances where the interference results in linear or convex penalization functions. We propose an exact algorithm for the general problem and polynomial-time algorithms for the other problems. The exact algorithm finds an optimal assignment in a reasonable time on small instances. The other two algorithms quickly find an optimal and a high-quality approximation assignment even if a problem is of considerable size. In contrast to conventional approximation methods, our algorithm provides the performance guarantee.

Recently researchers have approached the problem of motion planning with topological constraints. In such problems, the inputs to the planner are source and destination points and the output is expected to be a valid path that respects the topological constraints. A concrete example of such problems - and the topic of this paper - is planning for a robot which is connected with a cable of limited length to a fixed point in the operation space. This paper presents a planning method for such problems by examining how the configuration space manifold can be represented efficiently. We introduce a convenient method for generating either parts or the complete atlas for the manifold based on special “cable events”. Generating parts of the configuration space on-the-fly enables improvements over the state of the art: (a)we decompose the environment into cells as needed rather than an off-line global discretization, obtaining competitive time and space complexity for our planner, (b) we are able to exploit topological structure to represent robot-cable configurations concisely, (c) we generalize the representation in order to examine cable-to-cable contacts, which have been widely ignored in the literature until now. Our results show the efficiency of the method and indicate further promise for procedures that represent manifolds via an amalgamation of implicit discrete topological structure and explicit Euclidean cells.

Inspired by the Rapidly-exploring random tree data-structure and algorithm for path planning, we introduce an approach for spanning physical space with a group of simple mobile robots. Emphasizing minimalism and using only InfraRed and contact sensors for communication, our position unaware robots physically embody elements of the tree. Although robots are fundamentally constrained in the spatial operations they may perform, we show that the approach-implemented on physical robots- remains consistent with the original data-structure idea. In particular, we show that a generalized form of Voronoi bias is present in the construction of the tree, and that such trees have an approximate space-filling property. We present an analysis of the physical system via sets of coupled stochastic equations: the first being the rate-equation for the transitions made by the robot controllers, and the second to capture the spatial process describing tree formation. We are able to provide an understanding of the control parameters in terms of a process mixing-time and show the dependence of the Voronoi bias on an interference parameter which grows as O(√N).

We consider the problem of filtering whilst maintaining as little information as possible to perform a given task. The literature includes several illustrations of how adroit choices for state descriptions may lead to concise -or even minimal- filters tailored to specific tasks. We introduce an efficient algorithm which is able to reproduce these handcrafted solutions. Specifically, our algorithm accepts as input an arbitrary combinatorial filter, expressed as a transition graph, and outputs an equivalent filter that uses fewer information states to complete the same filtering task. We also show that solving this problem optimally is NP-hard, and that the related decision problem is NP-complete. These hardness results justify the potentially sub-optimal output of our algorithm. In the experiments we describe, our algorithm produces optimal or near-optimal reduced filters for a variety of problem instances. These reduced filters are of interest for several reasons, including their direct application on platforms with severely limited computational power and in systems that require communication over low-bandwidth noisy channels. Moreover, inspection of reduced filters may provide insights into the structure of a problem that can guide the design of the other elements of a robot system.

Many groups of agents exhibit emergent collective behaviors. The environment in which the agents operate is one determinant of the resulting behaviors. This work shows how automatic enumeration of environments enables exploration of various collective behaviors that perform useful group functions (e.g. segregation, corralling, shape formation). Although groups of agents, such as mobile robots, can be manipulated through explicit control, this study shows that these systems can be usefully manipulated without resorting to such imperative means. This method has obvious uses for heterogeneous robot systems, especially those which include large numbers of simple agents. The method introduced is general, in that it takes as input: (1) algorithmic specifications of the environment generation, (2) a black-box model of the individual agent's control laws, and (3) a mathematical description of the task objective. To show the validity of the proposed method this investigation studies two behaviors (splitting and corralling) for three commonly studied motion models, including the well known Reynold's model. Simulations and physical multi-robot trials show that automatically generated environments can elicit pre-specified behaviors from a group of individual agents. Additionally, this work investigates the effects of a group's emergent properties on the ability to elicit the specified behavior via the environment. The findings suggest that automatically exploring environments can lead to better exploration and understanding of collective behaviors, including the identification of previously unknown emergent behaviors.

Robotic clustering involves gathering spatially distributed objects into a single pile. It is a canonical task for self-organized multi-robot systems: several authors have proposed and demonstrated algorithms for performing the task. In this paper, we consider a setting in which heterogeneous strategies outperform homogeneous ones and changing the division of labor can improve performance. By modeling the clustering dynamics with a Markov chain model, we are able to predict performance of the task by different divisions of labor. We propose and demonstrate a method that is able to select an open-loop sequence of changes to the division of labor, based on this stochastic model, that increases performance. We validate our proposed method on physical robot experiments.

This paper addresses the problem of generating the simplest plans that solve robotic planning problems. Most robotic planning algorithms are concerned with producing plans that minimize execution cost, or generalizations of such costs. Motivated by circumstances with severe computational resource limits (e.g., memory or communication constrained settings), we instead address the problem of producing concise plans. In this work, conciseness is a measure of plan size that reflects the complexity of representing the plan explicitly. We seek a plan with minimal representational size, subject to correctness and completeness. We introduce a planning algorithm that generates concise plans for planning problems that may involve both non-determinism and partial observability, and also show that finding the most concise plan is an NP-hard problem, excusing the possible sub-optimality of our algorithm's output. We describe an implementation of the algorithm, along with empirical results on the run time and solution quality for both manipulation and navigation problem domains.

In scenarios in which new robots and tasks are added to a network of already deployed, interchangeable robots, a trade-off arises in minimizing the cost to execute the tasks and the level of disruption to the system. This paper considers a navigation-oriented variant of this problem and proposes a parametrizable method to adjust the optimization criterion: from minimizing global travel time (or energy, or distance), to minimizing interruption (i.e., obtaining the fewest number of robot reassignments), and mixtures in-between. Paths are computed by a task-allocation formulation in which the destinations of newly deployed robots are added to an existing allocation. We adapt the graph matching variant of the Hungarian algorithm-originally designed to solve the optimal assignment problem in complete graphs-to construct routing paths by showing that there is an interpretation of the sparse Hungarian bipartite graph in three dimensions. When new agent-task pairs are inserted, the assignment is reallocated in an incremental fashion in linear time (assuming traversal choices are limited in number). The algorithm is studied systematically in simulation and also validated with physical robots.

The Linear Complementarity Problem (LCP) is a key problem in robot dynamics, optimization, and simulation. Common experience with dynamic robotic simulations suggests that the numerical robustness of the LCP solver often determines simulation usability: if the solver fails to find a solution or finds a solution with significant residual error, interpenetration can result, the simulation can gain energy, or both. This paper undertakes the first comprehensive evaluation of LCP solvers across the space of multi-rigid body contact problems. We evaluate the performance of these solvers along the dimensions of solubility, solution quality, and running time.

Sensorless part orienting has proven useful in manufacturing and automation, while the manipulation of deformable objects is an area of growing interest. Existing sensorless orienting techniques may produce forces which have the potential to damage deformable parts. We present an algorithm that, when provided a geometric description of the part and a deformation model, generates a plan to orient the part up to symmetry from any initial orientation. The solution exploits deformation of the object under certain configurations to help resolve ambiguity. The approach has several attractive features: (1) the resulting plan is a short sequence of such actions guaranteed to succeed for all initial configurations; (2) the algorithm operates even with a very simple model of deformation, but is extensible when specialized knowledge is available; (3) failure to find a feasible solution has precise semantics (e.g., inadequate manipulator precision). We validate the algorithm experimentally with a pair of low-precision robot manipulators, orienting 6 parts made of 4 types of materials, with the correct orientation being reached on 80% of the 192 trials. Careful analysis of the failures emphasizes the importance of low-friction conditions, that increased manipulator precision would be beneficial but is not necessary, and a simple deformation model can suffice. In addition to illustrating the feasibility of sensorless manipulation of deformable parts, we note that the algorithm has applications to manipulation of non-deformable parts without the pressure switch sensor employed in existing sensorless orienting strategies.

A fundamental challenge in multi-robot systems is that global information is needed to succeed in some tasks, while the system's computation and sensing are fundamentally distributed. This paper considers the problem of estimating the relative density of robots in particular regions of the environment, but without wishing to incur the cost of obtaining a consistent metric representation. We compute a probability density function that describes positions of the robots within the system by leveraging properties of the underlying communication network. We introduce three different strategies for using and combining local measurements via a modified Parzen window kernel density method. The result is a representation that is most accurate near to the querying robot but which maintains qualitative properties of the global density. We argue that this a useful relaxation of the problem because it is meaningful from the perspective of the robots within the system itself. Validation takes the form of simulations with hundreds of simple robots.

Modeling contact in multibody simulation is a difficult problem frequently characterized by numerically brittle algorithms, long running times, and inaccurate (with respect to theory) models. We present a comprehensive evaluation of four methods for contact modeling on seven benchmark scenarios in order to quantify the performance of these methods with respect to robustness and speed. We also assess the accuracy of these methods where possible. We conclude the paper with a prescriptive description in order to guide the user of multibody simulation.

Many envisioned applications of multi-robot swarms involve the detection, production or maintenance of global structures through only local means. This paper introduces a scalable, distributed algorithm to approximately characterize important global geometric and topological properties. For a given spatial arrangement of robots, the algorithm estimates the longest network (geodesic) distance in any direction as well as the average Euclidean distance only using locally sensed information. In so doing, the robots need only to communicate with and sense (range and bearing) nearby robots. The algorithm uses a greedy method to approximate both distance metrics via parallel one-way message traversals. We provide a bound for the number of such traversals, showing a global characterization is produced in a running time that is sublinear in the total number of robots. Along with this analysis, we conduct simulations with hundreds of robots to validate the algorithm.

Flocking is a common and widely studied spatial behavior exhibited by groups. This work highlights inconsistencies in the presentation of motion rules used for flocking, by implementing the well known rule by Hamilton on a robot system. We address a common assumption regarding the form of input to the motion rule: detection of whole agents and suggest that such detection is not necessarily justified. Our multi-robot system successfully exhibits flocking behaviors using an alternative detection method based entirely on low level sensor data. Furthermore, we show (under certain parameter settings), the behaviors exhibited by the agent-based and sensor-based detection are equivalent. We also discuss the various dynamics and implications the chosen detection process has on the behaviors of a motion rule.

The introduction of two types of unmanned aerial vehicles into a production of A Midsummer Night's Dream suggests that social proof informs untrained human groups. We describe the metaphors used in instructing actors, who were otherwise untrained and inexperienced with robots, in order to shape their expectations. Audience response to a robot crash depended on whether the audience had seen how the actors interacted with the robot "baby fairies." If they had not seen the actors treating a robot gently, an audience member would likely throw the robot expecting it to fly or handle it roughly. If they had seen the actors with the robots, the audience appeared to adopt the same gentle style and mechanisms for re-launching the micro-helicopter. The difference in audience behavior suggests that the principle of social proof will govern how untrained humans will react to robots.

This paper describes a high-fidelity model of wireless propagation that integrates several existing models from the wireless communications literature. The model accounts for environmental features, including fading (large and small-scale, and multipath), link-layer models, and interference between radios. In addition to identification and integration of the complementary communication components, this paper's contribution is in demonstrating how discretization, approximation and batch pre-calculation allow the complete model to remain practicable for real-time robot simulation. The faithfulness of the simulated communications is assessed by showing how important qualitative aspects of the communication behavior are reproduced.

In this work, we further test the hypothesis that physical embodiment has a measurable effect on performance and impression of social interactions. Support for this hypothesis would suggest fundamental differences between virtual agents and robots from a social standpoint and would have significant implications for human-robot interaction. We have refined our task-based metrics to give a measurement, not only of the participant's immediate impressions of a coach for a task, but also of the participant's performance in a given task. We measure task performance and participants' impression of a robot's social abilities in a structured task based on the Towers of Hanoi puzzle. Our experiment compares aspects of embodiment by evaluating: (1) the difference between a physical robot and a simulated one; and (2) the effect of physical presence through a co-located robot versus a remote, tele-present robot. With a participant pool (n=21) of roboticists and non- roboticists, we were able to show that participants felt that an embodied robot w as more appealing and perceptive of the world than non-embodied robots. A larger pool of participants (n=32) also demonstrated that the embodied robot was seen as most helpful, watchful, and enjoyable when compared to a remote tele-present robot and a simulated robot.

Physical interference limits the utility of large-scale multi-robot systems. We present an empirical study of the effects of such interference in systems with hundreds of minimalist robots. We consider the canonical multi-robot foraging task, and define a new parametrized controller. This controller allows for evaluation of spatial arbitration strategies along a continuum with the traditional homogeneous and bucket-brigading algorithms at each end. We present data from thousands of simulations which suggests that methods surprisingly close to homogeneous foraging, but augmented with limited arbitration, can improve both performance and reliability

Autonomous robots are agents with physical bodies that share our environment. In this work, we test the hypothesis that physical embodiment has a measurable effect on performance and perception of social interactions. Support of this hypothesis would suggest fundamental differences between virtual agents and robots from a social standpoint and have significant implications for human-robot interaction. We measure task performance and perception of a robot's social abilities in a structured but open-ended task based on the Towers of Hanoi puzzle. Our experiment compares aspects of embodiment by evaluating: (1) the difference between a physical robot and a simulated one; (2) the effect of physical presence through a co-located robot versus a remote tele-present robot. We present data from a pilot study with 12 subjects showing interesting differences in perception of remote physical robot's and simulated agent's attention to the task, and task enjoyment.

This paper addresses the problem of directional audio beacon deployment. We describe how these beacons can be used on mobile robots to produce a system that can self-deploy and aid in disaster recovery efforts. A distributed algorithm that uses explicit communication to coordinate the deployment process is presented. The algorithm employs existing multi-robot task allocation methodologies and a procedure for clustering potential deployment locations in a problem domain-specific manner. Results from a sensor-based multi-robot simulation demonstrate that self-deploying beacons are indeed feasible and have the potential to decrease expected egress time. Furthermore, we show that the implementation is free of simulator-specific anomalies through trials with a group of physical robots.

This paper describes how environmental complexity measures can be employed in the process of validating experimental robotics work. We advocate the use of metrics that attempt to quantify the 'difficulty' of motion for a given environment. Space syntax methods (from the urban and building design literature) and fluid-flow models (used in crowd modeling) are described and proposed as relevant measures for mobile robotics domains. We show experimentally that these two metrics give very different expressions of complexity. We then discuss how, given their properties, these different metrics may be applied to robotics controller design and evaluation.