20 accepted papers
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 soluti…
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 question…
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 r…
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…
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…
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…
Scores of papers show, given some robots, how to improve the useful work they perform. Continuing this line, we consider the efficiency of robot experiments by examining the feasibility of conducting several experiments simultaneously, interleaving execution and sharing resources between them. This…
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 tim…
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…
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, wherei…
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…
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 env…
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…
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. Ou…
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…
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 th…
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 sp…
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 specifyi…
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 me…
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 rive…