30 accepted papers
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 g
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…
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 inc…
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 co…
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…
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 perc…
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…
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 m…
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…
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 exogeno…
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…
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…
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…
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…
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…
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…
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 ro…
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…
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 th…
Robot localization is the problem of determining a robot's pose in an environment, typically within a given map or a similar representation. Different methods have been proposed to address this localization problem for robots with limited sensing. In this letter, we present a localization method for
We consider multi-robot teams operating in uncertain dynamic settings where the costs used for computing task-allocations are not known exactly. In such cases, the desire to minimize the team's expected cost might need to be curtailed if, in doing so, the risk that results is intolerable. We describ
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 (improp…
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 ch…
We demonstrate manipulation of objects using the dynamics of a rope-like structure attached to a mobile robot as a passive tail. Three challenges arise in modeling and planning: the physics involved is nontrivial, the tail is underactuated, and motions of the object are nondeterministic. For such sy
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 en
For a given robot and a given task, this paper addresses questions about which modifications may be made to the robotâs suite of sensors without impacting the robotâs behavior in completing its task. Though this is an important design-time question, few principled methods exist for providing a d…
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 cluster…
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 cert…
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…