Dylan A. Shell

Reza H. Teshnizi, Dylan A. Shell

Considering an environment containing polygonal obstacles, we address the problem of planning motions for a pair of planar robots connected to one another via a cable of limited length. Much like prior problems with a single robot connected via a cable to a fixed base, straight line-of-sight visibility plays an important role. The present paper shows how the reduced visibility graph provides a natural discretization and captures the essential topological considerations very effectively for the two robot case as well. Unlike the single robot case, however, the bounded cable length introduces considerations around coordination (or equivalently, when viewed from the point of view of a centralized planner, relative timing) that complicates the matter. Indeed, the paper has to introduce a rather more involved formalization than prior single-robot work in order to establish the core theoretical result -- a theorem permitting the problem to be cast as one of finding paths rather than trajectories. Once affirmed, the planning problem reduces to a straightforward graph search with an elegant representation of the connecting cable, demanding only a few extra ancillary checks that ensure sufficiency of cable to guarantee feasibility of the solution. We describe our implementation of A${}^\star$ search, and report experimental results. Lastly, we prescribe an optimal execution for the solutions provided by the algorithm.

Grace McFassel, Dylan A. Shell

In studying robots and planning problems, a basic question is what is the minimal information a robot must obtain to guarantee task completion. Erdmann's theory of action-based sensors is a classical approach to characterizing fundamental information requirements. That approach uses a plan to derive a type of virtual sensor which prescribes actions that make progress toward a goal. We show that the established theory is incomplete: the previous method for obtaining such sensors, using backchained plans, overlooks some sensors. Furthermore, there are plans, that are guaranteed to achieve goals, where the existing methods are unable to provide any action-based sensor. We identify the underlying feature common to all such plans. Then, we show how to produce action-based sensors even for plans where the existing treatment is inadequate, although for these cases they have no single canonical sensor. Consequently, the approach is generalized to produce sets of sensors. Finally, we show also that this is a complete characterization of action-based sensors for planning problems and discuss how an action-based sensor translates into the traditional conception of a sensor.

Yulin Zhang, Dylan A. Shell

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.

Siddharth Mayya, Gennaro Notomista, Dylan Shell et al.

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 which coexist with lower robot densities in the domain. We envision a scenario where a swarm of vibration-driven robots---which sit atop bristles and achieve directed motion by vibrating them---move somewhat 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. This connection is a formal one and is a relatively recent result in studies of motility induced phase separation; it is previously unexplored in the context of robotics. 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.