Mapping Simple Polygons: How Robots Benefit from Looking Back

We consider the problem of mapping an initially unknown polygon of size n with a simple robot that moves inside the polygon along straight lines between the vertices. The robot sees distant vertices in counter-clockwise order and is able to recognize the vertex among them which it came from in its last move, i.e. the robot can look back. Other than that the robot has no means of distinguishing distant vertices. We assume that an upper bound on n is known to the robot beforehand and show that it can always uniquely reconstruct the visibility graph of the polygon. Additionally, we show that multiple identical and deterministic robots can always solve the weak rendezvous problem in which the robots need to position themselves such that all of them are mutually visible to each other. Our results are tight in the sense that the strong rendezvous problem, where robots need to gather at a vertex, cannot be solved in general, and, without knowing a bound beforehand, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known.     

Detection of robustly collision-free trajectories in unpredictable environments in real-time

One of the ultimate goals in robotics is to make robots of high degrees of freedom (DOF) work autonomously in real world environments. However, real world environments are unpredictable, i.e., how the objects move are usually not known beforehand. Thus, whether a robot trajectory is collision-free or not has to be checked on-line based on sensing as the robot moves. Moreover, in order to guarantee safe motion, the motion uncertainty of the robot has to be taken into account. This paper introduces a general approach to detect if a high-DOF robot trajectory is continuously collision-free even in the presence of robot motion uncertainty in an unpredictable environment in real time. Our method is based on the novel concept of dynamic envelope, which takes advantage of progressive sensing over time without predicting motions of objects in an environment or assuming specific object motion patterns. The introduced approach can be used by general real-time motion planners to check if a candidate robot trajectory is continuously and robustly collision-free (i.e., in spite of uncertainty in the robot motion).     

Asynchronous deterministic rendezvous in bounded terrains

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots’ trajectories until they meet. For each scenario, we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.     

Self-assembly strategies in a group of autonomous mobile robots

Robots are said to be capable of self-assembly when they can autonomously form physical connections with each other. By examining different ways in which a system can use self-assembly (i.e., different strategies), we demonstrate and quantify the performance costs and benefits of (i) acting as a physically larger self-assembled entity, (ii) letting the system choose when and if to self-assemble, (iii) coordinating the sensing and actuation of the connected robots so that they respond to the environment as a single collective entity. Our analysis is primarily based on real world experiments in a hill crossing task. The configuration of the hill is not known by the robots in advance—the hill can be present or absent, and can vary in steepness and orientation. In some configurations, the robots can overcome the hill more quickly by navigating individually, while other configurations require the robots to self-assemble to overcome the hill. We demonstrate the applicability of our self-assembly strategies to two other tasks—hole crossing and robot rescue—for which we present further proof-of-concept experiments with real robots.     

Collaborative Robot Exploration and Rendezvous: Algorithms, Performance Bounds and Observations

We consider the problem of how two heterogeneous robots can arrange to meet in an unknown environment from unknown starting locations: that is, the problem of arranging a robot rendezvous. We are interested, in particular, in allowing two robots to rendezvous so that they can collaboratively explore an unknown environment. Specifically, we address the problem of how a pair of exploring agents that cannot communicate with one another over long distances can meet if they start exploring at different unknown locations in an unknown environment.We propose several alternative algorithms that robots could use in attempting to rendezvous quickly while continuing to explore. These algorithms exemplify different classes of strategy whose relative suitability depends on characteristics of the problem definition. We consider the performance of our proposed algorithms analytically with respect to both expected- and worst-case behavior. We then examine their behavior under a wider set of conditions using both numerical analysis and also a simulation of multi-agent exploration and rendezvous. We examine the exploration speed, and show that a multi-robot system can explore an unknown environment faster than a single-agent system, even with the constraint of performing rendezvous to allow communication.We conclude with a demonstration of rendezvous implemented on a pair of actual robots.     

Gradual spatial pattern formation of homogeneous robot group

This paper proposes a gradual formation of a spatial pattern for a homogeneous robot group. The autonomous formation of spatial pattern is one of key technologies for the advancement of cooperative robotic systems because a pattern formation can be regarded as function differentiation of a multi-agent system. When multiple autonomous robots without a given local task cooperatively work for a global objective, the function differentiation is the first and indispensable step. For example, each member of cooperative insects or animals can autonomously recognize own local tasks through mutual communication with local members. There were a lot of papers that reported a spatial pattern formation of multiple robots, but the global information was supposed to be available in their approaches. It is however almost impractical assumption for a small robot to be equipped with an advanced sensing system for global localization due to robot’s scale and sensor size. The local information-based algorithm for the pattern formation is desired even if each robot is not equipped with a global localization sensor.We therefore propose a gradual pattern formation algorithm, i.e., a group of robots improves complexity of their pattern from to a simple pattern to a goal pattern like a polygon. In the algorithm, the Turing diffusion-driven instability theory is used so that it could differentiate roles of each robot in a group based only on local information. In experiment, we demonstrate that robots can make a few polygon patterns from a circle pattern by periodically differentiating robot’s roles into a vertex or a side. We show utilities of the proposed gradual pattern formation algorithm for multiple autonomous robots based on local information through some experiments.     

Editorial

The navigation capability of a group of robots can be improved by sensing of relative inter-robot positions and intercommunication of position estimates and planned trajectories. The cooperative navigation system (CNS) algorithm described here is based on a Kalman filter which uses inter-robot position sensing to update the collective position estimates of the group. Assuming independence of sensing and positioning errors, the CNS algorithm always improves individual robot estimates and the collective navigation performance improves as the number of robots increases. The CNS algorithm computation may be distributed among the robot group. Simulation results and experimental measurements on two Yamabico robots are described.     

Learning to select distinctive landmarks for mobile robot navigation

In landmark-based navigation systems for mobile robots, sensory perceptions (e.g., laser or sonar scans) are used to identify the robot’s current location or to construct internal representations, maps, of the robot’s environment. Being based on an external frame of reference (which is not subject to incorrigible drift errors such as those occurring in odometry-based systems), landmark-based robot navigation systems are now widely used in mobile robot applications.The problem that has attracted most attention to date in landmark-based navigation research is the question of how to deal with perceptual aliasing, i.e., perceptual ambiguities. In contrast, what constitutes a good landmark, or how to select landmarks for mapping, is still an open research topic. The usual method of landmark selection is to map perceptions at regular intervals, which has the drawback of being inefficient and possibly missing ‘good’ landmarks that lie between sampling points.In this paper, we present an automatic landmark selection algorithm that allows a mobile robot to select conspicuous landmarks from a continuous stream of sensory perceptions, without any pre-installed knowledge or human intervention during the selection process. This algorithm can be used to make mapping mechanisms more efficient and reliable. Experimental results obtained with two different mobile robots in a range of environments are presented and analysed.     

Deterministic Rendezvous in Graphs

Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees relies on fast network exploration and cannot be used when the graph contains cycles. We further study the simplest such network, i.e., the ring. We prove that, with simultaneous startup, optimal cost of rendezvous on any ring is Θ(D log l), where D is the initial distance between agents. We also establish bounds on rendezvous cost in rings with arbitrary startup. For arbitrary connected graphs, our main contribution is a deterministic rendezvous algorithm with cost polynomial in n, τ and log l, where τ is the difference between startup times of the agents. We also show a lower bound Ω (n²) on the cost of rendezvous in some family of graphs. If simultaneous startup is assumed, we construct a generic rendezvous algorithm, working for all connected graphs, which is optimal for the class of graphs of bounded degree, if the initial distance between agents is bounded.     

Planning of collision-free paths for a reconfigurable dual manipulator equipped mobile robot

In this paper, we study the problem of finding a collision-free path for a mobile robot which possesses manipulators. The task of the robot is to carry a polygonal object from a starting point to a destination point in a possibly culttered environment. In most of the existing research on robot path planning, a mobile robot is approximated by a fixed shape, i.e., a circle or a polygon. In our task planner, the robot is allowed to change configurations for avoiding collision. This path planner operates using two algorithms: the collision-free feasible configuration finding algorithm and the collision-free path finding algorithm. The collision-free feasible configuration finding algorithm finds all collision-free feasible configurations for the robot when the position of the carried object is given. The collision-free path finding algorithm generates some candidate paths first and then uses a graph search method to find a collision-free path from all the collision-free feasible configurations along the candidate paths. The proposed algorithms can deal with a cluttered environment and is guaranteed to find a solution if one exists.     

A Probabilistic Approach to Collaborative Multi-Robot Localization

This paper presents a statistical algorithm for collaborative mobile robot localization. Our approach uses a sample-based version of Markov localization, capable of localizing mobile robots in an any-time fashion. When teams of robots localize themselves in the same environment, probabilistic methods are employed to synchronize each robot's belief whenever one robot detects another. As a result, the robots localize themselves faster, maintain higher accuracy, and high-cost sensors are amortized across multiple robot platforms. The technique has been implemented and tested using two mobile robots equipped with cameras and laser range-finders for detecting other robots. The results, obtained with the real robots and in series of simulation runs, illustrate drastic improvements in localization speed and accuracy when compared to conventional single-robot localization. A further experiment demonstrates that under certain conditions, successful localization is only possible if teams of heterogeneous robots collaborate during localization.     

Differentially Flat Designs of Underactuated Open-Chain Planar Robots

A fully actuated system can execute any joint trajectory. However, if the system is underactuated, not all joint trajectories are attainable. For such systems, it is difficult to characterize attainable joint trajectories analytically. Numerical methods are generally used to characterize these. This paper investigates the property of differential flatness for underactuated planar open-chain robots and studies dependence on inertia distribution within the system. It is shown that certain choices of inertia distributions make an underactuated open-chain planar robot with revolute joints feedback linearizable, i.e., also differentially flat. Once this property is established, trajectory between any two points in the state space can be planned, and a controller can be developed to correct for errors. To demonstrate the proposed methodology in hardware, experiments with an underactuated 3-DOF planar robot are also presented.      

Oracle-based flocking of mobile robots in crash-recovery model

This paper considers a system of autonomous mobile robots that can move freely in a two-dimensional plane, and where a number of them can fail by crashing. The crash of a robot can be either permanent or temporary, that is, after its crash the robot either executes no action or it recovers from its failure. These robots repeatedly go through a succession of activation cycles during which they observe the environment, compute a destination and move. In particular, we assume weak robots, in the sense that robots cannot communicate explicitly between each other. Also, they cannot remember their past computations (i.e., they are oblivious). Finally, robots do not agree on a common coordinate system.In this paper, we address the fault-tolerant flocking problem under the crash-recovery model. That is, starting from any initial configuration, a group of non-faulty robots are required to form a desired pattern, and move together while following a robot leader moving on some trajectory, and keeping such a pattern in movement. Specifically, we propose a fault-tolerant flocking algorithm in the semi-synchronous model that allows correct robots to dynamically form a regular polygon in finite time, and maintain it in movement infinitely often. Our algorithm relies on the existence of two devices, namely an eventually perfect failure detector device to ensure failure detection, and also an eventual leader device to handle leader election. The algorithm tolerates permanent crash failures, and also crash-recovery failures of robots due to its oblivious feature. The proposed algorithm ensures the necessary restrictions on the movement of robots in order to avoid collisions between them. In addition, it is robust with respect to changes in the environment.     

Pursuit-Evasion on Trees by Robot Teams

We present Graph-Clear: a novel pursuit-evasion problem on graphs which models the detection of intruders in complex indoor environments by robot teams. The environment is represented by a graph, and a robot team can execute sweep and block actions on vertices and edges, respectively. A sweep action detects intruders in a vertex and represents the capability of the robot team to detect intruders in the region associated to the vertex. Similarly, a block action prevents intruders from crossing an edge and represents the capability to detect intruders as they move between regions. Both actions may require multiple robots to be executed. A strategy is a sequence of block and sweep actions to detect all intruders. When instances of Graph-Clear are being solved, the goal is to determine optimal strategies, i.e., strategies that use the least number of robots. We prove that for the general case of graphs, the problem of computation of optimal strategies is NP-hard. Next, for the special case of trees, we provide a polynomial-time algorithm. The algorithm ensures that throughout the execution of the strategy, all cleared vertices form a connected subtree, and we show that it produces optimal strategies.      

Highly Precise Dynamic Simulation Environment for Humanoid Robots

In this paper we present a simulation environment for humanoid robots with a precise and efficient method of handling ground contact, and experiments empirically validating the simulator. Highly accurate dynamic simulation is an essential tool for research and development in humanoid robotics, and a simulator should ideally provide a transparent interface with pathways for control and sensing information identical to those of the actual robot(s) it models. We identified ground contact as the chief source of divergence from reality in work to date and have tackled this problem by developing an algorithm for resolving ground contact for humanoid robots. Our objective was to produce an algorithm that is accurate, efficient and easy to implement. The algorithm is general with respect to the complexity of the foot model; is based on empirically measurable characteristics of the foot–ground interaction, i.e., friction, which we have obtained using experiments described; provides an exact implementation of the Coulomb friction model (avoiding polyhedral approximation of the friction cone); runs in real-time; is also amenable to a straightforward accuracy–speed trade-off; and is relatively easy to implement as a constraint selection method. The simulation environment embodies generality, and we have applied it to two different humanoid robots, Hoap-2 and CB. We present experiments comparing the results of simulation with identical motions performed by real robots, and comparing the full contact resolution algorithm, the modification trading accuracy for computational speed and a penalty-based method.     

Capturing a Convex Object With Three Discs

This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent disc-shaped robots. Given two stationary robots in contact with P, we characterize the set of positions of a third robot, the so-called capture region, that prevent P from escaping to infinity via continuous rigid motion. We show that the computation of the capture region reduces to a visibility problem. We present two algorithms for solving this problem, and for computing the capture region when P is a polygon and the robots are points (zero-radius discs). The first algorithm is exact and has polynomial time complexity. The second one uses simple hidden surface removal techniques from computer graphics to output an arbitrarily accurate approximation of the capture region; it has been implemented, and examples are presented.     

Classifying Environmental Features From Local Observations of Emergent Swarm Behavior

Robots in a swarm are programmed with individual behaviors but then interactions with the environment and other robots produce more complex, emergent swarm behaviors. One discriminating feature of the emergent behavior is the local distribution of robots in any given region. In this work, we show how local observations of the robot distribution can be correlated to the environment being explored and hence the location of openings or obstructions can be inferred. The correlation is achieved here with a simple, single-layer neural network that generates physically intuitive weights and provides a degree of robustness by allowing for variation in the environment and number of robots in the swarm. The robots are simulated assuming random motion with no communication, a minimalist model in robot sophistication, to explore the viability of cooperative sensing. We culminate our work with a demonstration of how the local distribution of robots in an unknown, office-like environment can be used to locate unobstructed exits.      

A novel approach to coordination of multiple robots with communication failures via proximity graph

In this paper, we investigate the coordination problem of multiple robots with limited communication ranges and communication failures. A novel rendezvous algorithm via proximity graph is developed so that the robot group can achieve rendezvous when the communication links satisfy an ergodic assumption. The convergence proof of the algorithm is established based on the tools from rooted graph theory. The effectiveness of the algorithm is illustrated by numerical examples in a 3D space.     

Moving formation convergence of a group of mobile robots via decentralised information feedback

In this article, a decentralised information feedback mechanism is introduced to a group of mobile robots such that the robots asymptotically converge to a given moving formation. It is assumed that the robots can exchange only position information according to a pre-specified communication graph. Each node represents a robot. Two robots are neighbours of each other if there is an edge between the two nodes. A feedback controller is performed for each robot by only using its own velocity information and the position information from its neighbours. It is proven that if the graph is connected, then the convergence to the moving formation of the closed-loop system is guaranteed. Several numerical simulations are presented to illustrate the results.     

Distributed formation control of nonholonomic mobile robots without global position measurements

This paper proposes a new class of distributed nonlinear controllers for leader-following formation control of unicycle robots without global position measurements. Nonlinear small-gain design methods are used to deal with the problem caused by the nonholonomic constraint of the unicycle robot and yield simple conditions for practical implementation. With the proposed distributed controllers, the formation control objective can be achieved without assuming any tree sensing structures. More interestingly, the distributed controller is robust to position measurement errors and the linear velocities of the robots can be restricted to specific bounded ranges.