We explore a navigation planning problem under uncertainty for a simple robot with extremely limited sensing. Our robot can turn subject to significant proportional error and move forward. As it moves in an environment with a known terrain map, the robot can detect changes in the terrain at its current position. Given an initial pose and a goal segment, the robot should find some sequence of actions to travel reliably from start to goal, if such a sequence exists. The resulting plan should guarantee the robot reaches the goal segment despite any movement errors experienced within some known error bound. In this paper, we propose an algorithm to find such an action sequence, implement and evaluate this algorithm, and present evidence for the feasibility of such an algorithm in an underwater navigation setting.

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.

Robotic systems are typically composed of various subsystems, such as localization and navigation, each encompassing numerous configurable components (e.g., selecting different planning algorithms). Once an algorithm has been selected for a component, its associated configuration options must be set to the appropriate values. Configuration options across the system stack interact nontrivially. Finding optimal configurations for highly configurable robots to achieve desired performance poses a significant challenge due to the interactions between configuration options across software and hardware that result in an exponentially large and complex configuration space. These challenges are further compounded by the need for transferability between different environments and robotic platforms. Data efficient optimization algorithms (e.g., Bayesian optimization) have been increasingly employed to automate the tuning of configurable parameters in cyber-physical systems. However, such optimization algorithms converge at later stages, often after exhausting the allocated budget (e.g., optimization steps, allotted time) and lacking transferability. This article proposes causal understanding and remediation for enhancing robot performance (CURE)—a method that identifies causally relevant configuration options, enabling the optimization process to operate in a reduced search space, thereby enabling faster optimization of robot performance.CUREabstracts the causal relationships between various configuration options and the robot performance objectives by learning a causal model in the source (a low-cost environment such as the Gazebo simulator) and applying the learned knowledge to perform optimization in the target (e.g.,Turtlebot 3physical robot). We demonstrate the effectiveness and transferability ofCUREby conducting experiments that involve varying degrees of deployment changes in both physical robots and simulation.

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.

The multi-robot visibility-based pursuit-evasion problem tasks a team of robots with systematically searching an environment to detect (capture) an evader. Previous techniques to generate search strategies for the pursuit team have shown to be either computationally intractable or permit poor solution quality. This paper presents a novel asymptotically optimal algorithm for generating a joint motion strategy for the pursuers. To explore the space of possible pursuer motion strategies, the algorithm utilizes a trio of hierarchical graph data structures that each capture certain elements of the problem such as connectivity (valid single pursuer motion), coordination (multiple pursuer motion), and tracking information (evaluating where an evader may be). The algorithm is inspired by well-known methods in the motion planning literature and inherits its asymptotic optimality from those techniques. In addition, we describe a method that can improve upon solutions found during the formative stages of the main algorithm, using a "fast-forward" approach that foregoes guarantees of asymptotic optimality, implementing heuristics that concentrate future samples into improving the path quality of the nominal solution. The algorithms were validated in simulation and results are provided.

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.

This paper introduces and solves a visibility-based escort planning problem. This novel problem, which is closely related to the well-researched family of visibility-based pursuit-evasion problems in robotics, entails an escort agent tasked with escorting a vulnerable agent, called the VIP, in a 2-dimensional environment. The escort protects the VIP from adversaries that pose line-of-sight threats. We describe a correct and complete planning algorithm whose inputs are a simply-connected polygonal map of the environment, starting locations for the escort and the VIP, along with a goal location to which the VIP agent should be safely moved. The algorithm computes trajectories for the escort and VIP which allow the VIP to reach its goal without coming into the line-of-sight of the adversary at any time. During the execution of these trajectories, the adversary is allowed to move along any continuous path that does not enter into the line-of-sight of the escort. The algorithm proceeds by dividing the environment into a collection of conservative regions and planning the escort's movements as a sequence of these regions via breadth-first search over an information graph. The trajectory of the VIP can then be constructed by tracing the ‘safe zones' swept out by the escort's trajectory. We describe an implementation of this algorithm and present computed examples of escort agent strategies in diverse environments.

This paper studies a multi-robot visibility-based pursuit-evasion problem in which a group of pursuer robots are tasked with detecting an evader within a two dimensional polygonal environment. The primary contribution is a novel formulation of the pursuit-evasion problem that modifies the pursuers' objective by requiring that the evader still be de-tected, even in spite of the failure of any single pursuer robot. This novel constraint, whereby two pursuers are required to detect an evader, has the benefit of providing redundancy to the search, should any member of the team become unresponsive, suffer temporary sensor disruption/failure, or otherwise become incapacitated. Existing methods, even those that are designed to respond to failures, rely on the pursuers to replan and update their search pattern to handle such occurrences. In contrast, the proposed formulation produces plans that are inherently tolerant of some level of disturbance. Building upon this new formulation, we introduce an augmented data structure for encoding the problem state and a novel sampling technique to ensure that the generated plans are robust to failures of any single pursuer robot. An implementation and simulation results illustrating the effectiveness of this approach are described.

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.

This paper presents a novel algorithm for monitoring marine environments utilizing a resource-constrained robot. Collecting water quality data from large bodies of water is paramount for monitoring the ecosystem's health, particularly for predicting harmful cyanobacteria blooms. The large spatial dimensions of such bodies of water and the slow varying of water quality parameters make exhaustive, complete coverage impractical and unnecessary. This work explores a new strategy for efficiently measuring water quality quantities with an autonomous surface vehicle (ASV). The method utilizes the medial axis of the water body producing a guideline for the ASV trajectory that visits representative areas of the environment. The proposed method ensures data collection in the narrower parts of the lake, where researchers have historically observed harmful blooms while also visiting open water areas. It also presents an analysis of the Spatio-temporal sensitivity of the target sensor. A comparison with the traditional lawnmower algorithm demonstrates that the conventional BCD-based complete coverage method cannot sample the small coves of a lake. As such, we show that the proposed method captures more diverse regions of the area with a partial coverage technique. Offline analysis of several lakes and reservoirs and results from field deployments at Lake Murray, SC, USA, demonstrate the proposed method's effectiveness.

During convergence, after a link state change in traditional networks with a distributed control plane, packets may get caught in transient forwarding loops. Such loops can be avoided by imposing a certain order among the routers in updating their forwarding information bases (FIBs), but it requires some form of coordination among routers. As an alternative, a progressive link metric increment method has been proposed for loop-free forwarding without ordered FIB updates, but it takes longer to converge to the target state. In this paper, we show that the order of updates rarely matters for loop-free convergence when the failure inference-based fast reroute (FIFR) scheme with interface-specific forwarding is employed for dealing with link failures. The key insight is to have each router install the traditional interface-independent forwarding entries as soon as they are recomputed during convergence and install the recomputed interface-specific backwarding entries post-convergence. Our evaluation of 280 real and random topologies confirms that the order of updates does not matter with the proposed approach for 17336 out of 17339 links in those topologies. To handle such rare cases where the order matters, it can be coupled with progressive link metric increments to ensure loop-freedom with unordered FIB updates. Thus, the proposed approach, referred to as FIFR++, makes it possible to achieve disruption-free fast convergence and fast reroute without requiring any modification to the IP datagram and without needing any coordination between routers.

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.

Given a two-dimensional polygonal space, the multi-robot visibility-based pursuit-evasion problem tasks several pursuer robots with the goal of establishing visibility with an arbitrarily fast evader. The best known complete algorithm for this problem takes time doubly exponential in the number of robots. However, sampling-based techniques have shown promise in generating feasible solutions in these scenarios. One of the primary drawbacks to employing existing sampling-based methods is that existing algorithms have long execution times and high failure rates for complex environments. This paper addresses that limitation by proposing a new algorithm that takes an environment as its input and returns a joint motion strategy which ensures that the evader is captured by one of the pursuers. Starting with a single pursuer, we sequentially construct Sample-Generated Pursuit-Evasion Graphs to create such a joint motion strategy. This sequential graph structure ensures that our algorithm will always terminate with a solution, regardless of the complexity of the environment. We describe an implementation of this algorithm and present quantitative results that show significant improvement in comparison to the existing algorithm.

This paper addresses the visibility-based pursuit-evasion problem where a team of pursuer robots operating in a two-dimensional polygonal space seek to establish visibility of an arbitrarily fast evader. This is a computationally challenging task for which the best known complete algorithm takes time doubly exponential in the number of robots. However, recent advances that utilize sampling-based methods have shown progress in generating feasible solutions. An aspect of this problem that has yet to be explored concerns how to ensure that the robots can recover from catastrophic failures which leave one or more robots unexpectedly incapable of continuing to contribute to the pursuit of the evader. To address this issue, we propose an algorithm that can rapidly recover from catastrophic failures. When such failures occur, a replanning occurs, leveraging both the information retained from the previous iteration and the partial progress of the search completed before the failure to generate a new motion strategy for the reduced team of pursuers. We describe an implementation of this algorithm and provide quantitative results that show that the proposed method is able to recover from robot failures more rapidly than a baseline approach that plans from scratch.

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.

Visual monitoring operations underwater require both observing the objects of interest in close-proximity, and tracking the few feature-rich areas necessary for state estimation. This paper introduces the first navigation framework, called AquaVis, that produces on-line visibility-aware motion plans that enable Autonomous Underwater Vehicles (AUVs) to track multiple visual objectives with an arbitrary camera configuration in real-time. Using the proposed pipeline, AUVs can efficiently move in 3D, reach their goals while avoiding obstacles safely, and maximizing the visibility of multiple objectives along the path within a specified proximity. The method is sufficiently fast to be executed in real-time and is suitable for single or multiple camera configurations. Experimental results show the significant improvement on tracking multiple automatically-extracted points of interest, with low computational overhead and fast re-planning times.Accompanying short video: https://youtu.be/JKO bbrIZyU

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.

Combinatorial filters are formal structures for filtering and reasoning over discrete sensor data. This article presents a series of results addressing the question whether thefilter minimization(FM) problem, an NP-hard problem of state-space reduction on such filters, and a variant of it, thefilter partitioning minimization(FPM) problem, which requires the reduced filter to partition the state space of the original filter, can be solved via quotient operations under equivalence relations of the state space. We first consider the well-known notion ofbisimulationand show that, although bisimulation always yields feasible solutions to FM and FPM problems, it does not necessarily induce optimal solutions. We also establish a connection between filter reduction and the notion ofsimulation; specifically, we show that the FM problem is equivalent to the problem of inducing a minimal filter that simulates a given filter. We then introduce a variant of bisimulation, which we callcompatibility, and prove that the FPM problem can always be solved by computing the quotient of the input filter under acompatibility equivalencerelation having a minimum number of equivalence classes. On the other hand, computing optimal solutions to the FM problem requires to look for relations beyond equivalence relations, and in fact, the FM problem can be solved by computing the quotient of the original filter under a closed covering of the state space with the minimum number of compatibility classes. Subsequently, we introduce two special relations,the union of all compatibility relationsandthe mergeability relation, which are both computable in polynomial time. By analyzing where these two relations become an equivalence relation, we identify several classes of filters for which FM and FPM problems are solvable in polynomial time.

This paper is about the closely-related problems of localization and aggregation for extremely simple robots, for which the only available action is to move in a given direction as far as the geometry of the environment allows. Such problems may arise, for example, in biomedical applications, wherein a large group of tiny robots moves in response to a shared external stimulus. Specifically, we extend the prior work on these kinds of problems presenting two algorithms for localization in environments with curved (rather than polygonal) boundaries and under low-friction models of interaction with the environment boundaries. We present both simulations and physical demonstrations to validate the approach.

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.

Navigation underwater traditionally is done by keeping a safe distance from obstacles, resulting in "fly-overs" of the area of interest. Movement of an autonomous underwater vehicle (AUV) through a cluttered space, such as a shipwreck or a decorated cave, is an extremely challenging problem that has not been addressed in the past. This paper proposes a novel navigation framework utilizing an enhanced version of Trajopt for fast 3D path-optimization planning for AUVs. A sampling-based correction procedure ensures that the planning is not constrained by local minima, enabling navigation through narrow spaces. Two different modalities are proposed: planning with a known map results in efficient trajectories through cluttered spaces; operating in an unknown environment utilizes the point cloud from the visual features detected to navigate efficiently while avoiding the detected obstacles. The proposed approach is rigorously tested, both on simulation and in-pool experiments, proven to be fast enough to enable safe real-time 3D autonomous navigation for an AUV.

In this paper, we consider a temporal logic planning problem in which the objective is to find an infinite trajectory that satisfies an optimal selection from a set of soft specifications expressed in linear temporal logic (LTL) while nevertheless satisfying a hard specification expressed in LTL. Our previous work considered a similar problem in which linear dynamic logic for finite traces (LDLf), rather than LTL, was used to express the soft constraints. In that work, LDLfwas used to impose constraints on finite prefixes of the infinite trajectory. By using LTL, one is able not only to impose constraints on the finite prefixes of the trajectory, but also to set `soft' goals across the entirety of the infinite trajectory. Our algorithm first constructs a product automaton, on which the planning problem is reduced to computing a lasso with minimum cost. Among all such lassos, it is desirable to compute a shortest one. Though we prove that computing such a shortest lasso is computationally hard, we also introduce an efficient greedy approach to synthesize short lassos nonetheless. We present two case studies describing an implementation of this approach, and report results of our experiment comparing our greedy algorithm with an optimal baseline.

This paper addresses the problem of planning for visibility-based pursuit evasion, in contexts where the pursuer robot may experience some positioning errors as it moves in search of the evader. Specifically, we consider the case in which a pursuer with an omnidirectional sensor searches a known environment to locate an evader that may move arbitrarily quickly. Known algorithms for this problem are based on decompositions of the environment into regions, followed by a search for a sequence of those regions through which the pursuer should pass. In this paper, we note that these regions can be arbitrarily small, and thus that the movement accuracy required of the pursuer may be arbitrarily high. To resolve this limitation, we introduce the notion of an ε-robust solution strategy, in which ε is an upper bound on the positioning error that the pursuer may experience. We establish sufficient conditions under which a solution strategy is ε-robust, and introduce an algorithm that determines, for a given environment, the largest value of ε for which a solution strategy satisfying those sufficient conditions exists. We de-scribe an implementation and show simulated results demonstrating the effectiveness of the approach.

This paper addresses the problem of multi-robot coordination in scenarios where the robots may experience unexpected delays in their movements. Prior work by Čáp, Gregoire, and Frazzołi introduced a control law, called RMTRACK, which enables robots in such scenarios to execute preplanned paths in spite of disturbances in the execution speed of each robot, while guaranteeing that each robot can reach its goal without collisions and without deadlocks. We extend that approach to handle scenarios in which the disturbance probabilities are unknown at the start and non-uniform across the environment. The key idea is to `repair' a plan on-the-fly, by swapping the order in which a pair of robots passes through a mutual collision region (i.e. a coordination space obstacle), when making such a change can be estimated to improve the overall performance of the system. We introduce a technique based on Gaussian Processes to estimate future disturbances, and propose two algorithms for testing, at appropriate times, whether a swap of a given obstacle would be beneficial. Tests in simulation demonstrate that our algorithm achieves significantly smaller average travel time than RMTRACK at only a modest computational expense.

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.

We study the problem of covering an environment using an Unmanned Aerial Vehicle (UAV) with limited battery capacity. We consider a scenario where the UAV can land on an Unmanned Ground Vehicle (UGV) and recharge the onboard battery. The UGV can also recharge the UAV while transporting the UAV to the next take-off site. We present an algorithm to solve a new variant of the area coverage problem that takes into account this symbiotic UAV and UGV system. The input consists of a set of boustrophedon cells - rectangular strips whose width is equal to the field-of-view of the sensor on the UAV. The goal is to find a tour for the UAV that visits and covers all cells in minimum time. This includes flight time for visiting and covering all cells, recharging time, as well as the take-off and landing times. We show how to reduce this problem to a known NP-hard problem, Generalized Traveling Salesperson Problem (GTSP). Given an optimal GTSP solver, our approach finds the optimal coverage paths for the UAV and UGV. We evaluate our algorithm through simulations and proof-of-concept experiments.

This paper aims to improve the practical scalability of automated tools to assist in designing robots. Such problems rapidly become intractable because the underlying design space is immense. We consider a specific type of design tool addressed in prior work, which constructs a representation of the destructiveness boundary in the space of robot designs. This prior work showed that a legible representation, specifically a decision tree, of this boundary can illuminate which elements of a sensing or actuation system are most important for enabling the robot to complete its task. In that context, the robot's interaction with the world is represented as procrustean graph, and the space of robot designs is represented by the space of label maps that rewrite the labels on that graph. In this paper, we expand upon those results by showing how domain knowledge can enable such tools to find solutions to more complex problems within a reasonable time frame. Specifically, we propose three different scenarios, expressed as constraints on the p-graph and on the label maps, under which the learning algorithm to identify the destructiveness boundary can converge quickly to high accuracy results for problems at larger scales than the prior, general-purpose algorithm. The conditions for each of these scenarios are easily verifiable and the set of problems that fall under each is rich enough to encompass several interesting problems. Experimental results demonstrate the effectiveness of the proposed methods.

Environmental monitoring and surveying operations on rivers currently are performed primarily with manually-operated boats. In this domain, autonomous coverage of areas is of vital importance, for improving both the quality and the efficiency of coverage. This paper leverages human expertise in river exploration and data collection strategies to automate and optimize these processes using autonomous surface vehicles (ASVs). In particular, three deterministic algorithms for both partial and complete coverage of a river segment are proposed, providing varying path length, coverage density, and turning patterns. These strategies resulted in increases in accuracy and efficiency compared to human performance. The proposed methods were extensively tested in simulation using maps of real rivers of different shapes and sizes. In addition, to verify their performance in real world operations, the algorithms were deployed successfully on several parts of the Congaree River in South Carolina, USA, resulting in total of more than 35km of coverage trajectories in the field.

In this paper, we address the problem of temporal logic planning given both hard specifications of the robot's mission and soft preferences on the plans that achieve the mission. In particular, we consider a problem whose inputs are a transition system, a linear temporal logic (LTL) formula specifying the robot's mission, and an ordered sequence of formulas expressed in linear dynamic logic over finite traces (LDLf) specifying the user's preferences for how the mission should be completed. The planner's objective is to synthesize, on this transition system, an infinite trajectory that best fits the user's preferences over finite prefixes of that trajectory while nonetheless satisfying the overall objective. We describe an algorithm for this problem that constructs, from the inputs, a product automaton -which is, in fact, a special kind of state-weighted Büchi automaton- over which an optimal trajectory is synthesized. This synthesis problem is solved via reduction to the minimax path problem in vertex weighted graphs, which can be solved by variants of the standard algorithms for computing shortest paths in a graph or by algorithms for the all-pairs bottleneck paths problem on vertex-weighted graphs. We show the applicability of the approach via some case studies, for which we present results computed by an implementation.

This paper is focused on providing fast reroute and loop-free convergence in traditional IP networks, without making any modifications to the IP datagram and without requiring any coordination between routers for FIB updates. Failure inference based fast route (FIFR) is an approach in which routers adjacent to a failed link or router perform local rerouting around the failure, without notifying non-adjacent routers about the failure. The non-adjacent routers utilize interface-specific forwarding tables, which are precomputed based on potential inferred failures that could cause a packet for a given destination to arrive through that unusual interface, to ensure loop-free forwarding towards the destination. However, as long as the failure lasts, packets that were to be forwarded over the failed link traverse suboptimal paths, as they reach the router adjacent to the failure and then are rerouted along a detour. Therefore, in case of a long-lasting failure, it is desirable to trigger a network-wide link state update, so that all routers can converge to new optimal forwarding tables. But, without some coordination between routers to install their forwarding entries in a specific order, there may be transient forwarding loops during the convergence period. As we are interested in a mechanism that does not require any such coordination between routers, we consider the possibility of employing progressive link state updates. In this paper, we show that FIFR with progressive link metric increments can guarantee loop-free forwarding not only before/after but during convergence too and protect against non-partitioning single link failures.

In large scale coverage operations, such as marine exploration or aerial monitoring, single robot approaches are not ideal, as they may take too long to cover a large area. In such scenarios, multi-robot approaches are preferable. Furthermore, several real world vehicles are non-holonomic, but can be modeled using Dubins vehicle kinematics. This paper focuses on environmental monitoring of aquatic environments using Autonomous Surface Vehicles (ASVs). In particular, we propose a novel approach for solving the problem of complete coverage of a known environment by a multi-robot team consisting of Dubins vehicles. It is worth noting that both multi-robot coverage and Dubins vehicle coverage are NP-complete problems. As such, we present two heuristics methods based on a variant of the traveling salesman problem-k-TSP-formulation and clustering algorithms that efficiently solve the problem. The proposed methods are tested both in simulations to assess their scalability and with a team of ASVs operating on a 200 km2lake to ensure their applicability in real world.

Combinatorial filters are discrete structures for modeling and reasoning about robotic systems. Such filters are of interest not only because of the potential for reduction of the computational power needed to execute the filter, but also for the insight they can sometimes provide into the information requirements of certain robotic tasks. It is known that the filter minimization problem -that is, for a given filter, to find a combinatorial filter with the minimal number of states among all filters with equivalent behavior-is NP-hard. Intuition might suggest that the well-known notion of bisimulation might be of direct use for this minimization problem. Indeed, the bisimilarity relation -the union of all bisimulation relations over the state space of the original filter-is an equivalence relation, and one might attempt to reduce a filter by merging states that are equivalent under this relation. This paper studies this relationship between bisimulation and combinatorial filter reduction. Specifically, we show that every filter minimization problem can be solved by computing a quotient of the input filter with some relation, but that for some filters, the bisimilarity relation is not the correct relation for this purpose. We also characterize the result of the bisimulation quotient operation as the solution to a different, stricter filter minimization problem, and identify several classes of filters for which a variant of bisimulation, called compatibility, can be used to minimize filters in polynomial time.

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.

We consider the problem of coverage planning for a particular type of very simple mobile robot. The robot must be able to translate in a commanded direction (specified in a global reference frame), with bounded error on the motion direction, until reaching the environment boundary. The objective, for a given environment map, is to generate a sequence of motions that is guaranteed to cover as large a portion of that environment as possible, in spite of the severe limits on the robot's sensing and actuation abilities. We show how to model the knowledge available to this kind of robot about its own position within the environment, show how to compute the region whose coverage can be guaranteed for a given plan, and characterize regions whose coverage cannot be guaranteed by any plan. We also describe a heuristic algorithm that generates coverage plans for this robot, based on a search across a specially-constructed graph. Simulation results demonstrate the effectiveness of the approach.

We consider a visibility-based pursuit-evasion problem in which a single robot with an omnidirectional but unreliable sensor moving through an environment must systematically search that environment to detect an unpredictably moving target. A common assumption in visibility-based pursuit-evasion is that the sensors used to detect the evader are perfectly reliable. That is, any evader that moves within view of the pursuer for any interval of time will be detected. This assumption is problematic because, when implemented on real sensor systems, such plans cannot account for the possibility of short-term false negative errors in evader detection. This paper addresses this limitation by introducing a model based on the idea of pessimal unoccluded distance to reason about the degree of plausibility that the evader may be concealed within each occluded region. We describe a decomposition of the environment that fully characterizes the opportune moment for an evader to take advantage of sensor error. Furthermore, we present a complete algorithm that solves the active problem of planning a search for a pursuer which maximizes the distance that the evader must travel through the pursuer robot's sensor footprint.

This paper addresses the problem of generating coverage paths-that is, paths that pass within some sensor footprint of every point in an environment-for vehicles with Dubins motion constraints. We extend previous work that solves this coverage problem as a traveling salesman problem (TSP) by introducing a practical heuristic algorithm to reduce runtime while maintaining near-optimal path length. Furthermore, we show that generating an optimal coverage path is NP-hard by reducing from the Exact Cover problem, which provides justification for our algorithm's conversion of Dubins coverage instances to TSP instances. Extensive experiments demonstrate that the algorithm does indeed produce length paths comparable to optimal in significantly less time.

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.)

This paper studies the feasibility of minimizing convergence delay and forwarding disruption without carrying any additional bits in the IP header, to provide high availability despite link failures in traditional IP networks. Previously proposed mechanisms achieve two of these three objectives by trading off the other objective. For instance, the ordered forwarding information base updates approach may prolong the convergence delay, whereas the SafeGuard scheme requires carrying the path cost in the IP header. As a better alternative, we propose a scheme called fast convergence with fast reroute (FCFR), which combines the features of IP fast rerouting and interface-specific forwarding. We show that FCFR can achieve minimal convergence delay, while ensuring loop-free delivery during convergence, after a single non-partitioning failure in an IP network, without altering the IP header format, making it amenable for immediate deployment.

We introduce a complete algorithm for solving a pursuit-evasion problem in a simply-connected two-dimensional environment, for the case of a single pursuer equipped with fixed beam sensors. The input for our algorithm is an environment and a collection of sensor directions, in which each is capable of line-of-sight detection in a fixed direction. The output is a pursuer motion strategy that ensures the detection of an evader that moves with unbounded speed, or a statement that no such strategy exists. The intuition of the algorithmis to decompose the environment into a collection of convex conservative regions, within which the evader cannot sneak between any pair of adjacent sensors. This decomposition induces a graph we call the pursuit-evasion graph (PEG), such that any correct solution strategy can be expressed as a path through the PEG. For an instance defined by m beams and an environment with n vertices, the algorithm runs in time O(2mn2). We implemented the algorithm in simulation and present some computed examples illustrating the algorithm's correctness.

This paper addresses the problem of robot global localization in a known environment, in the presence of many dynamic obstacles. Deploying a robot in crowded spaces such as museums, shopping malls, department stores, or university campuses is especially challenging because the moving people occlude the static parts of the environment, such as walls and doorways, making the robot essentially blind. A new weighting function is proposed for a particle filter state estimation algorithm that accounts for the presence of dynamic obstacles and avoids population depletion. An active localization strategy is employed which guides the robot to locations that resolve ambiguities and eliminate hypotheses in a systematic manner. Experimental results from multiple simulations and from real robot deployments validate the localization improvements achieved by the proposed method.

We describe a new decentralized algorithm for multi-robot systems to form arbitrary repeated lattice patterns. Prior work showed how to represent a desired pattern using a directed graph in which each edge is labeled with a rigid body transformation, and proposed an algorithm that accepts this graph as input and computes destinations for each robot using only local information. In this paper, we improve upon that result by describing a new algorithm, substantially different both in message passing procedure and in movement strategy, to resolve several limitations of the existing algorithm. We prove that, by executing this algorithm, the robots will form the desired lattice pattern in a bounded amount of time. We further show that, if the robots' communication graph is connected at the start of the algorithm, it will remain connected throughout the algorithm's execution. Using a simulation, we demonstrate that this algorithm works correctly for systems with dozens of autonomous robots to form various lattice patterns. Moreover, the experiments show a significant improvement in solution quality for our new algorithm compared to the previous approach.

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.

We present an algorithm that uses a sparse collection of noisy sensors to characterize the observed behavior of a mobile agent. Our approach models the agent's behavior using a collection of randomized simulators called implicit agent models and seeks to classify the agent according to which of these models is believed to be governing its motions. To accomplish this, we introduce an algorithm whose input is an observation sequence generated by the agent, represented as sensor label-time pairs, along with an observation sequence generated by one of our implicit agent models and whose output is a measure of the similarity between the two observation sequences. Using this similarity measure, we propose two algorithms for the model classification problem: one based on a weighted voting scheme and one that uses intermediate resampling steps. We have implemented these algorithms in simulation, and present results demonstrating their effectiveness in correctly classifying mobile agents.

In this paper, we propose a decentralized algorithm to form arbitrary repeating formations of multiple robots. Methods are known to form specific kinds of repeating structures such as squares, triangles, and hexagons by modeling each robot as a particle that responds to attractive and repulsive forces generated by nearby robots. However, such methods are generally designed by hand for one specific type of lattice. Our approach is more general, in the sense that we present a single algorithm, for which a description of the desired repeating pattern is part of the input. We represent this pattern as a directed graph, in which edges show the desired rigid body transformations between the local frames of pairs of neighbor robots. The robots autonomously organize themselves into a family of rooted trees, and use these trees to perform task assignments locally and without conflicts. We show, via our simulated implementation, that our algorithm works for robot systems with hundreds of robots to form various lattice patterns. Our experiments also show that the approach can recover rapidly from robot failures, even if those failures impact a large fraction of the robot population.

We introduce a centralized algorithm for a visibility-based pursuit-evasion problem in a two-dimensional environment for the case of multiple pursuers. The input for our algorithm is an environment represented as a doubly-connected edge list and the initial positions of the pursuers. The output is a joint strategy for the pursuers that guarantees that the evader has been captured, or a statement that no such strategy exists. We create a Cylindrical Algebraic Decomposition(CAD) of the joint configuration space by using polynomials that capture where critical changes can occur to the region of the environment hidden from the pursuers. Then after computing the adjacency graph for the CAD we construct a Pursuit Evasion Graph(PEG) induced by the adjacency graph. A search through the PEG can produce one of the following outcomes; the search can reach a vertex where the pursuers' motions up to this point ensure that the evader has been captured, or the search terminates without finding a solution and produces a statement recognizing that no solution exists.

We introduce a probabilistically complete algorithm for solving a visibility-based pursuit-evasion problem in two-dimensional polygonal environments with multiple pursuers. The inputs for our algorithm are an environment and the initial positions of the pursuers. The output is a joint strategy for the pursuers that guarantees that the evader has been captured. We create a Sample-Generated Pursuit-Evasion Graph (SG-PEG) that utilizes an abstract sample generator to search the pursuers' joint configuration space for a pursuer solution strategy that captures the evaders. We implemented our algorithm in simulation and provide results.

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.

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 this work we consider a navigation problem for a very simple robot equipped with only a map, compass, and contact sensor. Our prior work on this problem uses a graph to navigate between the convex vertices of an environment. In this paper, we extend this graph with the addition of a new node type and four new edge types. The new node type allows for more uncertainty in robot position. The presence of one of these new edge types guarantees reliable transitions between these nodes. This enhanced graph enables the algorithm to navigate environment features not solvable by our previous algorithm, including T-junctions and long halls. We also present a heuristic to accelerate the planning process by prioritizing the promising edge tests to perform. Our heuristic effectively focuses the search and qualitative data show that it computes plans with much less computational effort than a naïve approach. We describe a simulated implementation of the algorithm that finds paths not previously possible, and a physical implementation that demonstrates the feasibility of executing those plans in practice.

This paper describes and analyzes a new technique for reasoning about uncertainty called constrained geometric approximation (CGA). We build upon recent work that has developed methods to explicitly represent a robot's knowledge as an element, called an information state, in an appropriately defined information space. The intuition of our new approach is to constrain the I-state to remain in a structured subset of the I-space, and to enforce that constraint using appropriate over-approximation methods. The result is a collection of algorithms that enable mobile robots with extreme limitations in both sensing and computation to maintain simple but provably mean-ingful representations of the incomplete information available to them. We present a simulated implementation of this technique for a sensor-based navigation task, along with experimental results for this task showing that CGA, compared to a high-fidelity representation of the un-approximated I-state, achieves a similar success rate at a small fraction of the computational cost.

We present an algorithm that computes a minimal-cost pursuer trajectory for a single pursuer to solve the visibility-based pursuit-evasion problem in a simply-connected two-dimensional environment. This algorithm improves upon the known algorithm of Guibas, Latombe, LaValle, Lin, and Motwani, which is complete but not optimal. Our algorithm uses a Tour of Segments (ToS) subroutine to construct a pursuer path that minimizes the distance traveled by the pursuer while guaranteeing that all evaders in the environment will be captured. We have implemented our algorithm in simulation and provide results.

This paper addresses the problem of using a distributed team of tracking robots to maintain proximity to a collection of unpredictably moving targets. Each tracker is equipped with short range communication hardware and a low resolution sensor that can detect the presence of targets, but not their precise locations, their identities, nor even the number of targets within the sensing range. We present methods for set-membership-based filtering that exploit specific structures in the information space for this problem. We also describe an active algorithm that allows the tracker team to follow the targets in a coordinated way, in spite of the incomplete information and intermittent communication links. A simulation of this algorithm shows that the passive filtering algorithm maintains an accurate representation of each tracker's knowledge, and that the active tracking algorithm is able to leverage this information to achieve accurate, robust target tracking.

We propose an algorithm for a visibility-based pursuit-evasion problem in a simply-connected two-dimensional environment, in which a single pursuer has access to a probabilistic model describing how the evaders are likely to move in the environment. The application of our algorithm can be best viewed in the context of search and rescue: Although the victims (evaders) are not actively trying to escape from the robot, it is necessary to consider the task of locating the victims as a pursuit-evasion problem to obtain a firm guarantee that all of the victims are found. We present an algorithm that draws sample evader trajectories from the probabilistic model to compute a plan that lowers the Expected Time to Capture the evaders without drastically increasing the Guaranteed Time to Capture the evaders. We introduce a graph structure that takes advantage of the sampled evader trajectories to compute a path that would "see" all the evaders if they followed only those trajectories in our sampled set. We then use a previous technique to append our path with actions that provide a complete solution for the visibility-based pursuit evasion problem. The resulting plan guarantees that all evaders are located, even if they do not obey the given probabilistic motion model. We implemented the algorithm in a simulation and provide a quantitative comparison to existing methods.

Wireless sensor networks are vulnerable to various attacks and network dynamics that can breach data privacy and harm data availability. Since those threats cannot be addressed purely by cryptography-based methods, this paper presents a data dissemination scheme that can enhance two goals: data privacy and data availability, leveraging the node location diversity presented in typical wireless sensor networks rather than relying on cryptographic techniques. We demonstrate that the message content is important to quantify the uncertainty associated with data privacy and data availability, and provide content-based definitions utilizing information states. Further, to strike the balance between two conflicting goals in an energy efficient way, we construct a spatial privacy graph based on the locations of network nodes, and use a distributed coloring scheme to ensure that any pairs of nodes whose combined data provide too much information should not send their sensed data to the same storage node. Additionally, sensor nodes selectively send data to multiple storage nodes to achieve higher availability. Our experimental results show that our scheme can achieve better data privacy and a higher level of data availability at smaller energy cost than other baseline data dissemination schemes.

We consider a navigation problem for a robot equipped with only a map, compass, and contact sensor. In addition to the limitations placed on sensing, we assume that there exists some bounded uncertainty on rotations of our robot, due to precision errors from the compass. We present an algorithm providing guaranteed transitions in the environment between certain pairs of points. The algorithm chains these transitions together to form complete navigation plans. The simplicity of the robot's design allows us to concentrate on the nature of the navigation problem, rather than the design and implementation of our robotic system. We illustrate the algorithm with an implementation and simulated results.

Target tracking problems have been extensively studied for both robots and sensor networks. In this paper, we consider a target tracking problem in which a sensorless tracking robot must maintain close proximity to an unpredictably moving target. To assist the robot, a network of sensor nodes, each equipped with a binary proximity sensor, is spread through the environment. This architecture has the benefit of eliminating the need for information-rich sensors on the tracker, while supplying it with nonlocal observations of the target. However, it also introduces new complications due to the mobility of the tracker and the energy limitations of the sensor nodes. To address these issues, we present algorithms that allow both the tracker and the sensor nodes to maintain partial information about the target's location. The contribution of this work is an algorithm that manages the propagation of information across this network, making message delivery decisions on-the-fly, based on each message's informative value for the tracker. We present an implementation along with simulation results. The results show that our system achieves both good tracking precision and low energy consumption in both start-up and steady state phases of the problem, and that its performance is superior to that of earlier methods for this problem.

Existing target tracking algorithms require the tracker to have access to information-rich sensors, and may have difficulty recovering when the target is out of the tracker's sensing range. In this paper, we present a target tracking algorithm that combines an extremely simple mobile robot with a networked collection of wireless sensor nodes, each of which is equipped with an unreliable, limited-range, Boolean sensor for detecting the target. The tracker maintains close proximity to the target using only information sensed by the network, and can effectively recover from temporarily losing track of the target. Our approach combines a protocol for the sensor network that conserves energy by dynamically adjusting the time-to-live for packets it transmits with a reactive strategy for the tracker based on its information state. We present an implementation along with experimental results. Our experimental results show that our system achieves both good tracking precision and low energy consumption.

Researchers have addressed the localization problem for mobile robots using many different kinds of sensors, including rangefinders, cameras, and odometers. In this paper, we consider localization using a robot that is virtually "blind", having only a clock and contact sensor at its disposal. This represents a drastic reduction in sensing requirements, even in light of existing work that considers localization with limited sensing. We present probabilistic techniques that represent and update the robot's position uncertainty and algorithms to reduce this uncertainty. We demonstrate the experimental effectiveness of these methods using a Roomba autonomous vacuum cleaner robot in laboratory environments.

Robots must complete their tasks in spite of unreliable actuators and limited, noisy sensing. In this paper, we consider the information requirements of such tasks. What sensing and actuation abilities are needed to complete a given task? Are some robot systems provably "more powerful" than others? Can we find meaningful equivalence classes of robot systems? This line of research is inspired by the theory of computation, which has produced similar results for abstract computing machines. The basic idea is a dominance relation over robot systems that formalizes the idea that some robots are stronger than others. We show that this definition is directly related to the robots' ability to complete tasks. Our prior work in this area assumes perfect control and sensing, requires that the robot begin with a single fixed initial condition within a known environment, and models of time as a sequence of variable-length discrete stages, rather than as a continuum. In this paper, we substantially improve upon that earlier work by addressing these problems.

Localization is a fundamental problem for many kinds of mobile robots. Sensor systems of varying ability have been proposed and successfully used to solve the problem. This paper probes the lower limits of this range by describing three extremely simple robot models and addresses the active localization problem for each. The robot, whose configuration is composed of its position and orientation, moves in a fully-known, simply connected polygonal environment. We pose the localization task as a planning problem in the robot's information space, which encapsulates the uncertainty in the robot's configuration. We consider robots equipped with: 1) angular and linear odometers; 2) a compass and contact sensor and; 3) an angular odometer and contact sensor. We present localization algorithms for models 1 and 2 and show that no algorithm exists for model 3. An implementation with simulation examples is presented.

This paper presents a global localization technique for a robot with only linear and angular odometers. The robot, whose configuration is composed of its position and orientation, moves in a fully-known environment by alternating rotations and forward translations. We pose the problem as a discrete-time planning problem in the robot's information space, which encapsulates the uncertainty in the robot's configuration. Our contribution is to show that in any simply-connected, bounded polygonal environment, localization by odometry alone is possible, but only up to the symmetries in the environment

We present a localization method for robots equipped with only a compass, a contact sensor and a map of the environment. In this framework, a localization strategy can be described as a sequence of directions in which the robot moves maximally. We show that a localizing sequence exists for any simply connected polygonal environment by presenting an algorithm for computing such a sequence. We have implemented the algorithm and we present several computed examples. We also show that the sensing model is minimal by showing that replacement of the compass by an angular odometer precludes the possibility of performing localization.

We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of piecewise-linear paths is given on which the two robots move. The robots have a maximum speed and are capable of instantly switching between any two arbitrary speeds. Each robot would like to minimize its travel time independently. The Pareto-optimal solutions are the ones for which there exist no solutions that are better for both robots. The algorithm computes exact solutions in time O(mn/sup 2/ log n), in which m is the number of paths in the roadmap, n is the number of coordination space vertices. An implementation is presented.