PhD Thesis: Scalable Localization and Coordination of Robot Swarms

As the capabilities of robots and their control systems improve, applications involving the use of large robot swarms in semi-structured environments become increasingly viable. Such applications include the progressive automation of warehouses, factories, mine sites and hospitals. Despite differences in context and application, these problems all require accurate localization and timely coordination of large fleets of robots.

In outdoor applications, satellite-based localization (e.g. GPS) is a core technology driving the development of autonomous vehicles and facilitating the progressive robotization of industries such as agriculture, mining, inspection and freight. Satellite-based localization enables such applications by providing robots with the ability to quickly and independently measure their absolute position. In indoor environments, satellite-based localization is unavailable, making absolute positioning in such environments challenging.

The first contribution of this thesis is the development of a scalable, “indoor GPS”-like system using ultra-wideband radio technology. The topology of this system is similar to that of GPS: fixed-position radio modules installed in the environment regularly transmit radio signals, fulfilling a similar role to that of GPS satellites; while mobile robots move within the coverage area and localize themselves based on the received signals. Much like GPS, the system therefore scales to support an unlimited number of robots. Theoretical developments presented in this thesis are supported by experimental results, including a demonstration of the system’s functionality, in which multiple nano-quadcopters are flown simultaneously within a space.

Generating collision-free trajectories for large swarms of robots operating in close proximity is a similarly challenging problem, since robot trajectories are coupled through collision avoidance constraints, making the problem computationally expensive and time consuming to solve using classical optimization techniques. The second contribution of this thesis is a method to quickly generate such trajectories by leveraging the parallel-computation architecture of modern graphics processing units. The effectiveness and scalability of this method is demonstrated in two simulation-based case studies: a benchmark problem requiring a swarm of 200 quadcopters to traverse a maze; and an example in which a fleet of 100 robots with bicycle dynamics must change their formation. In both cases, the method easily handles nonlinear dynamics and constraints, and generates feasible, collision-free trajectories for the entire swarm in a matter of seconds.

The developments and contributions presented in this thesis provide a pathway towards the application of these technologies to the localization and coordination of large robot swarms in indoor environments.


Fast generation of collision-free trajectories for robot swarms using GPU acceleration

As the capabilities of robots and their control systems improve, we see an increasing number of use-cases where the simultaneous operation of robots within a space is advantageous. Although trajectories for individual robots can be computed quickly using existing methods, when robots operate simultaneously and in close proximity, the requirement for collision avoidance introduces a coupling between robot trajectories and makes the trajectory generation problem difficult to solve quickly. In this paper we propose a parallelizable formulation of such problems and a method for solving them quickly on modern graphics processing units, using momentum-based gradient descent. We demonstrate the proposed framework in simulation using two case studies: a swarm of 200 quadcopters traversing a maze, and a fleet of 100 bicycle robots changing their formation. In both cases, our method requires just seconds to generate feasible, collision-free trajectories for the entire swarm.

More Information Source Code Download

Self-Calibrating Ultra-Wideband Network Supporting Multi-Robot Localization

In this paper we concern ourselves with the development of a localization system that permits multiple robots to localize themselves simultaneously within a given area, which has been outfitted with a network of stationary radio modules. We derive a clock synchronization scheme for the radio modules, show how each module is able to compute its position within the network, and finally demonstrate how multiple robots are able to operate simultaneously within the space by using time-difference-of-arrival measurements to localize themselves. Since robots are passive receivers in this system and are able to compute their position based only on received and local information, multiple robots can operate simultaneously and without the need for central coordination or centralized localization infrastructure. All results presented in this paper are supported by experimental results, and the functionality of the system is demonstrated by multiple micro-quadrocopters localizing and flying simultaneously within a space.

More Information Download

Augmenting Ultra-Wideband Localization with Computer Vision for Accurate Flight

Ultra-wideband radio networks enable low-cost, low-computation robot localization in semi-structured environments; however, previous results have shown that these localization systems suffer from spatially-varying measurement biases, leading to a spatially-varying offset between the physical and the estimated position. In tasks where absolute positioning or high tracking accuracy is required, this offset can lead to failure of the task. This paper proposes augmenting ultra-wideband-based localization with visual localization to improve estimation accuracy for critical tasks. It also presents a control strategy that takes the camera measurement process into account, and allows the ultra-wideband system’s measurement biases to be learned and compensated over multiple executions of the task. This bias compensation can be used to improve the accuracy of the task in the case of visual impairment. The effectiveness of the proposed framework is demonstrated by accurately flying a quadrocopter to a landing platform using on-board estimation and control.


System Identification of the Crazyflie 2.0 Nano Quadrocopter

Accurate control and state estimation require an accurate mathematical model of a system. This Bachelor thesis takes a first principles approach to the modelling and identification of the major parameters that govern the flight of a Crazyflie 2.0 nano-quadrocopter. These parameters have since been incorporated into the Crazyflie 2.0 as part of it’s extended Kalman filter, non-linear controller and model-based power-distribution framework.


A Robot Self-Localization System using One-Way Ultra-Wideband Communication

A robot localization system is presented that enables a robot to estimate its position within some space by passively receiving ultra-wideband radio signals from fixed-position modules. Communication from the fixed-position modules is one-way, allowing the system to scale to multiple robots. Furthermore, the system’s high position update rate makes it suitable to be used in a feedback control system, and enables the robot to track and perform high-speed, dynamic motions.

This paper describes the algorithmic underpinnings of the system, discusses design decisions and their impact on the performance of the resulting localization, and highlights challenges faced during implementation. Performance of the localization system is experimentally verified through comparison with data from a motion-capture system. Finally, the system’s application to robot self-localization is demonstrated through integration with a quadrocopter.


Fusing ultra-wideband range measurements with accelerometers and rate gyroscopes for quadrocopter state estimation

A state estimator for a quadrocopter is presented, using measurements from an accelerometer, angular rate gyroscope, and a set of ultra-wideband ranging radios. The estimator uses an extended aerodynamic model for the quadrocopter, where the full 3D airspeed is observable through accelerometer measurements. The remaining quadrocopter states, including the yaw orientation, are rendered observable by fusing ultra-wideband range measurements, under the assumption of no wind. The estimator is implemented on a standard microcontroller using readily-available, low-cost sensors. Performance is experimentally investigated in a variety of scenarios, where the quadrocopter is flown under feedback control using the estimator output.

Download Errata

The Flight Assembled Architecture Installation: Cooperative construction with flying machines

The art installation “Flight Assembled Architecture” is one of the first structures built by flying vehicles. Culminating in a 6m-tall tower composed of 1500 foam modules, the installation was assembled by four quadrocopters in 18 hours during a four-day-long live exhibition at the Regional Contemporary Art Fund Center in Orléans, France. This article documents the design and development of specific elements of the autonomous system behind this one-of-a-kind installation and describes the process and challenges of bringing such a complex system out of the laboratory and into the public realm, where live demonstration and human-in-the-loop interaction demand high levels of robustness, dependability, and safety. The installation is a 1:100 scale model of what was originally conceived as a 600 m-high vertical village and is an exploration of aerial construction in architecture.


Knowledge Transfer for High-Performance Quadrocopter Maneuvers

Iterative Learning Control algorithms are based on the premise that “practice makes perfect”. By iteratively performing an action, repetitive errors can be learned and accounted for in subsequent iterations, in a non-causal and feed-forward manner. This method has been previously implemented for a quadrocopter system, enabling the quadrocopter to learn to accurately track high-performance slalom trajectories. However, one major limitation of this system is that knowledge from previously learned trajectories is not generalized or transferred to new trajectories; these must be learned from a state of zero experience.

This paper experimentally shows that the major dynamics of the Iterative Learning Control process can be captured by a linear map, trained on previously learned slalom trajectories. This map enables this prior knowledge to be used to improve the initialization of an unseen trajectory. Experimental results show that prediction based on a single prior is enough to reduce the initial tracking error for an unseen trajectory by an order of magnitude.