In this paper, we present deformable configuration control - a fully distributed algorithm that allows multiple robots to deform their configuration to avoid various shapes of obstacles while maintaining connectivity. Robots contacted with an obstacle first estimate the width of an obstacle by sharing bumped status of individual robots, and choose an appropriate obstacle avoidance scenarios between obstacle detouring and bouncing off a wall. Second, for both scenarios, robots switch their motion model to a parent following motion to avoid the obstacle. Finally, robots keep sensing the maximum tree angle to estimate whether they are completely escaped from the obstacle, and return to flock formation motion model. We provide theoretical analysis about maintaining connectivity while robots are avoiding an obstacle. Simulation results show a group of 36 robots successfully avoid three different kinds of obstacles including 1) a small bar, 2) a narrow corridor, and 3) a large wall while maintaining connectivity.

We present and analyze methods for patrolling and surveillance in an environment with a distributed swarm of robots with limited capabilities. Our approach is based on a distributed triangulation of the work space, in which a set of p stationary sensors provides coverage control; in addition, there are r mobile robots that can move between the sensors. Building on our prior work on structured exploration of unknown spaces with multi-robot systems, we can make use of a triangulation that is constructed in a distributed fashion and guarantees good local navigation properties, even when sensors and robots have very limited capabilities.

This paper presents a distributed approach for exploring and triangulating an unknown region using a multirobot system. The resulting triangulation is a physical data structure that is a: compact representation of the workspace, contains distributed knowledge of each triangle, builds the dual graph of the triangulation, and supports reads and writes of auxiliary data. Our algorithm builds a triangulation in a closed two-dimensional Euclidean environment, starting from a single location. It provides coverage with a breadth-first search pattern and completeness guarantees. We show that the computational and communication requirements to build and maintain the triangulation and its dual graph are small. We then present a physical navigation algorithm that uses the dual graph, and show that the resulting path lengths are within a constant factor of the shortest-path Euclidean distance. Finally, we validate our theoretical results with experiments on triangulating a region with a system of low-cost robots. Analysis of the resulting triangulation shows that most of the triangles are of high quality, and cover a large area. Implementation of the triangulation, dual graph, and navigation all use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.

Positioning a group of robots at the center of their geodesic Voronoi cells minimizes the worst-case response time for any robot to arrive at an exogenous event in the workspace. We construct these cells in a distributed fashion, building on our prior work on triangulating unknown spaces with multi-robot systems. This produces a physical data structure - a set of triangles formed by the positions of the robots that can be used to perform coverage control. This paper presents: 1) A discrete approximation of the geodesic Voronoi cell using the multi-robot triangulation. We call this a topological Voronoi cell, and show that it can be computed efficiently in a distributed fashion and with theoretical guarantees compared to continuous version. 2) A local motion controller to guide navigating robots to the centroid of their topological Voronoi cell. This controller uses bounded communications with a fixed constant, but can produce local extrema that trap navigating robots away from the optimal position. 3) An enhanced local controller using navigation agents to help guide the navigating robot to the optimal position in its Voronoi cell. It also uses bounded communications, but with a constant that can be tuned to trade communications bandwidth for increased accuracy. 4) Hardware experiments that compute the topological Voronoi cell on a group of 14 robots, simulation results that demonstrate local extrema, and the effectiveness of the virtual navigation agents, and simulation results comparing the performance of the patrolling algorithm using and not using topological Voronoi cells.

In this paper, we present flocking with cohesive configuration control - motion controllers that allow multiple robots to move through the environment as a coherent group while maintaining connectivity and density invariants. We start with a flocking controller from the literature. First, we produce a boundary force on robots that are on the internal and external boundaries of the configuration. This removes concave regions of the boundary, producing a convex configuration with uniform density. Second, we solve interstitial lattice errors caused by robots clumping too close together by moving them towards the boundary with a clump remover algorithm. Finally, we determine when a configuration is on the verge of disconnecting by identifying local articulation points; regions where the removal of a single robot will change the local topology. When one is detected, we switch modes to a clustering algorithm that draws robots to the vulnerable region. The combination of these algorithms produces a cohesive configuration controller. We verify our resulting controller with simulations from random initial conditions and selected extreme cases. Simulation results show the controller successfully forms a configuration with natural resting density in twelve of trials and maintains connectivity in twelve trials. We also provide real-world experiments to show that proposed algorithms work under low-resolution sensor platforms.

No abstract available.

This paper deals with a path planning problem for turning motion of a car-like vehicle. We propose a turning method which finds a curvature continuous optimal path between two positions for a car-like vehicle.