Sage Journals: Discover world-class research

Abstract

In this article, we present a novel high-performance millirobot ( m illi- rob ot- To ronto), designed to allow for the testing of complex swarm-behaviours, including human–swarm interaction. m illi- rob ot- To ronto, built only with off-the-shelf components, has locomotion, processing and sensing capabilities that significantly improve upon existing designs, while maintaining one of the smallest footprints among current millirobots. As complementary software to this hardware development, herein, we also present a new global swarm-topology estimation algorithm. The method is novel in that it uniquely fuses incomplete location data collected by the individual robots in a distributed manner to optimally estimate the topology of the overall swarm using a centralized computer. It is a generalized technique usable by any swarm comprising robots capable of collecting location estimates of neighbouring robots. Numerous experiments, evaluating the performance of m illi- rob ot- To ronto and the proposed optimal swarm-topology estimation algorithm, are also included.

Keywords

Mobile millirobots swarm-topology estimation human–swarm interactions

Introduction

Small robots, typically categorized as milli-, micro- or nanorobots,^1
–3 have applications in a variety of areas. Some applications include use in surveillance,^4
–6 wilderness search and rescue,^7

–11 urban search and rescue,^12
–14 medicine,^15,16 micro-assembly¹⁷ and wireless sensor networks.^18,19 In the work of Kashino et al.,^7,8 a millirobot was used to perform wilderness search and rescue experiments in a scaled-down lab environment. Fearing¹² suggested to use millirobots to locate survivors in a collapsed building by spreading through narrow and complex passages. Yim et al.¹⁶ proposed a wireless biopsy method wherein a soft capsule (pill) robot equipped with a camera and wireless communication module is actuated inside the human body. In the work of Vartholomeos et al.,¹⁷ high-precision motion of a millirobot demonstrated the potential to use them for micro-assembly tasks. Other designs of note include self-folding origami robots,²⁰ bio-inspired legged robots^21,22 and units that can pull objects heavier than their own body weight.²³

Millirobots have also been used as research tools in testing swarm algorithms that aim to have a group of decentralized, self-organizing agents exhibiting collective behavior.²⁴ Such small, cost-effective robots have allowed scientists to study both autonomous and supervised swarm tasks in confined workspaces with hardware experimentations.^25,26

In the above context, our focus has been on the design of a novel high-performance millirobot, m illi- rob ot- To ronto ( mROBerTO ), to allow for the testing of complex swarm-behaviours via physical robots, including human–swarm interaction (HSI).^27
–29 mROBerTO is built only with off-the-shelf components and has locomotion, processing and sensing capabilities that significantly improve upon existing designs.

Furthermore, herein, we also present a new method for swarm-topology estimation that utilizes the capabilities of mROBerTO to estimate the overall topology of the swarm. The method is novel in that it uniquely fuses incomplete data, collected in a distributed manner, using a centralized algorithm. It should be noted that, while the method was designed with mROBerTO in mind, it is a generalized technique. Namely, any swarm, comprising robots capable of collecting location estimates of neighbouring robots, could utilize the proposed method.

Millirobot designs

Millirobot designs for swarm applications reported in the literature include GRITSBot,³⁰ TinyTeRP,^31,32 Wanda,³³ AMiR,^34,35 Jasmine ³⁶ and Alice II. ³⁷ Alice II, for example, incorporates watch motors for locomotion, can be equipped with a linear camera and supports radio communication. However, it is limited in processing power and cannot detect proximity or bearing information of its neighbours. Jasmine is equipped with micro direct current (DC) motors and utilizes six infrared (IR) emitter/receiver pairs for all-around sensing and communication coverage. TinyTeRP uses geared motors and has an all-terrain add-on. GRITSBot achieves locomotion with micro stepper motors, comprises three stacked layers, each with varying sensors, and has all-direction IR sensing coverage. AMiR allows for modularity, where one such application is the incorporation of microphones for detecting neighbours. However, as does TinyTeRP, it has limited processors, and thus, local processing of received signals and local communications are not implemented.

Other millirobots include the Kilobot³⁸ and the Colias. ³⁹ Kilobot uses a single IR LED for communication with its neighbours and achieves motion using two coin-shaped vibration motors. Colias is a 40 × 40 mm2 robot that can move up to a speed of 350 mm/s.

Larger swarm robots (>75 × 75 mm2 footprint) have also been reported on, such as the E-Puck,⁴⁰ the SwarmBot⁴¹ and the R-One. ^42,43 These have a wide range of sensory capabilities, high-performance processors and relatively long battery lives.

Only a few millirobots, such as the E-Puck and the Kilobot, are commercially available.^44,45 Furthermore, due to their small sizes, the above-mentioned units have been be limited in their communication, locomotion and sensing capabilities.⁴⁶ Locomotion selection and design have proved to be, particularly, challenging since conventional technologies do not scale well downward and are often limited in terms of power output. This has made it difficult for researchers to test complex swarm algorithms via currently available physical millirobots, including unknown environment exploration,^26,47,48 target searching^49,50 and HSI.^46,51

Herein, thus, our goal is to present a novel millirobot with a combination of high-performance processing, sensing, communication and locomotion features developed to overcome some of the design limitations of earlier small millirobots. These advanced features are achieved while keeping the unit size comparable to the smallest existing millirobots. The proposed design has a novel sensing module for localizing neighbouring robots without requiring their relocation or the use of anchors.

Swarm-localization and topology estimation

Typical swarm behaviours, such as distributed sensing for obstacle avoidance, and area coverage, have been achieved using classical physics-based techniques, where only neighbouring robots interact.^46,52 Furthermore, the algorithms developed have been evaluated in controlled environments with simple problem instances (e.g. minimal obstacles with few robots).⁵³ More complex behaviours, such as swarm-formation management, require robots to have greater knowledge regarding the overall global state of the swarm including the positions of all the robots (e.g. tasks that feature irregular swarm formations and task allocations in dynamic environments).^50,54 Such position knowledge is also essential in HSI scenarios, where the human supervisor needs knowledge regarding the state of the swarm to guide it towards completing tasks such as foraging, searching for and localizing a radiation source, and search and rescue missions.^{26,46,49,51,55,56}

Estimating the locations of swarm members, for purposes such as those discussed above, is termed swarm localization and is, typically, an online process.²⁶ Online localization can be carried out either using an external infrastructure^57,58 or on-board sensors,^{59

–71} where the latter is more robust as it eliminates reliance on structures or entities outside of the swarm. Range-based methods of localization using on-board sensors, which require the robots in the swarm to directly measure their relative proximity and bearing with respect to other neighbouring robots, are common.⁵⁹ However, such algorithms require either for the robots to be in motion (i.e. relocated)^60

–64 or at least one robot to act as an anchor with known global coordinates.^65

–71 Furthermore, there have been only a few studies showing the implementation of localization algorithms via physical robots and, even when they are, experiments have been restricted to two or three robots at most.^63,64

Information acquired through localization can be used to address the topology estimation problem, where the objective is to recover the ‘shape’ of the swarm. Previous research, primarily, considered the calculation of a set of statistical parameters to define the topology of the swarm.^72,73 In the work of Lantao et al.,⁷² for example, estimates of the longest network distance between any two robots, in any direction, as well as the average distance between robots are used for this purpose. Similarly, Freeman et al.⁷³ describe an algorithm for estimating summary statistics, such as the swarm’s inertial moments, that describe the shape of the swarm. However, research on the direct use of robot relative positions to estimate a swarm’s topology has not been so far reported in the literature.

In this article, thus, we present a novel global swarm-topology estimation method that calculates the detailed swarm topology via the relative positions of all robots with respect to each other. It uniquely utilizes incomplete data sets of relative robot positions and bearings to estimate the overall topology of the swarm that can be used for HSI experiments. It comprises a unique combination of distributed and centralized computing to reap the benefits of both. The algorithm is a generalized technique. It can be utilized by any swarm with robots capable of obtaining location estimates of neighbouring robots (as can mROBerTO).

Problem statement

As outlined above, millirobots often have limited sensing and communication capabilities and are difficult to build due to their small size. These factors complicate their use for swarm-behaviour studies, especially, in the case of HSI experiments. The first problem addressed in this article, therefore, is one of designing a high-performance millirobot for HSI that is of similar size to the smallest existing millirobots. Additionally, the millirobot should be easy to build and maintain despite its small size.

In terms of capabilities, a swarm robot for HSI requires reliable locomotion, advanced processing and sensing capabilities and long-range (wireless) communication ability. Namely, a swarm robot needs to efficiently and effectively communicate with and sense other robots in its vicinity. It could benefit from modularity to allow for future improvements.

As also above-mentioned, an essential part of HSI is swarm-topology estimation. In remote HSI, the human supervisor interacting with the swarm will, typically, not be able to observe the swarm directly. Instead, the supervisor must rely on information gathered from the robots to estimate the state of the swarm. One key swarm-state variable that is often important to the supervisor is swarm topology (i.e. where the robots are relative to one another). It is, therefore, necessary to present an accompanying swarm-topology estimation algorithm when advocating a robot design for HSI studies. To this end, given our proposed robot’s capabilities, the second problem addressed in this article is swarm-topology estimation.

In the swarm-topology estimation problem addressed herein, the only sensors available to observe the swarm must be on-board the robots themselves. Data acquired are, therefore, limited in scope to what the robots can sense and collect. Since swarm robots interact locally, each robot would only be able to acquire information regarding other robots in its vicinity. The objective of swarm-topology estimation is to effectively fuse incomplete data sets acquired by the robots in order to provide the supervisor with an estimate of the complete swarm topology.

Overview of University of Toronto milli-robot design

A new ground swarm robot was designed and built at the University of Toronto – mROBerTO.^27
–29 The design is novel in that it has a simple modular architecture, utilizes a high-power processor with integrated wireless communication and has a sensing module capable of localizing neighbouring robots in a decentralized manner without the need for robots to relocate or use anchors. It is the first millirobot to be designed with remote HSI studies in mind, incorporating both wireless and local communication into its base design.

As noted above, the 16 × 16 × 32 mm3 mROBerTO was designed to have advanced capabilities, while being comparable in size to existing millirobots, and utilizing only off-the-shelf components that are easy to source. It comprises four modules: the locomotion module, the processing and communication module and two sensing modules – proximity sensing and swarm sensing(see Figure 1).^27,28 mROBerTO ’s locomotion module contains all the components necessary to enable robot motion: two DC motors, an H-bridge for driving the motors and voltage regulators to provide power. Motion control is achieved using a kinematic model of the robot and a calibrated translator between desired motor angular velocities and pulse width modulation (PWM) levels. The processing and communication module of mROBerTO is connected to all other modules. The module holds the robot’s central processing unit, a Nordic nRF51422 system-on-chip. The chip is a 32-bit ARM Cortex-M0 processor with integrated ANT+^TM and Bluetooth® Smart communication capabilities. mROBerTO has two sensing modules: one, at the front of the robot, for proximity sensing, and a second, at the top, for swarm sensing (see Figure 1). The two sensing modules can be modified/adapted to allow for additional sensing capabilities without affecting the core functionality of the robot or increasing its volume.

Figure 1.

mROBerTO’s exploded-assembly (front and back views). mROBerTO: m illi- rob ot- To ronto.

Each of the above-mentioned modules, as well as their integration, is described in detail in the work of Kim et al.^27,28 and Drisdelle et al.²⁹ – as such, they are omitted herein. The specific description of the swarm-sensing module below, thus, is only due to its immediate relevance to the swarm-topology estimation algorithm proposed in this article. A video describing mROBerTO and demonstrating its operation can be seen in YouTube.⁷⁴

The swarm-sensing module

The swarm-sensing module of mROBerTO enables swarm-behaviour monitoring and formation control. Namely, it was designed for localized communication and localization. This module has six IR detectors and four emitters at the edges of the module, allowing for all-direction coverage, as shown in Figure 2.

Figure 2.

Swarm-sensing module with six IR detectors on top and four emitters on the bottom.

IR was selected for its usability in concurrent localization and communication. Six detectors were used to make full use of the analogue-to-digital converters available and maximize the angular resolution of measurements. Four emitters were used, as this was enough for all-around coverage. This module also houses a secondary microcontroller, an ATmega328, which is tasked with the processing of the received IR signals. The processing tasks include signal modulation and demodulation as well as signal interpretation to acquire proximity and bearing information.

An mROBerTO can acquire proximity and bearing information from other robots while remaining static (i.e. they do not need to relocate). In contrast, other millirobots of similar size, such as Alice II,³⁷ Jasmine ³⁶ and TinyTeRP,³¹ can only obtain proximity and bearing information by requiring their neighbours to move for triangulation.^60

–63,65

Swarm-topology estimation

In HSI scenarios, a human supervisor can provide assistance either through direct commands or guidance to individual robots or to the swarm.^51,55 A key swarm-state that must be, thus, real-time observable to the supervisor is the swarm’s topology. For example, in both swarm-formation management and location-dependent task allocation in large swarms, knowing the swarm’s topology is essential for effective decision-making.

Typically, a swarm would operate in a remote location away from the human supervisor, who would have no way of directly observing the swarm, for example, via overhead sensors. Thus, herein, we present a new global swarm-topology estimation method that only utilizes information collected from the swarm robots and transmitted to a central computer. The algorithm is novel in that it only utilizes partial location data sets obtained from individual robots and fuses them to estimate the full swarm topology. Furthermore, the algorithm does not require prior knowledge of the global position of any of the swarm members or surrounding environment features.

The proposed swarm-topology estimation method consists of two phases: (I) distributed relative localization, through data acquisition from the swarm robots, and (II) swarm-topology estimation, via a central computer (see Figure 3).

Figure 3.

A two-phased global swarm-topology estimation method.

The first phase is carried out using the on-board processing and sensing capabilities of mROBerTOs, where each robot determines the relative locations of its respective neighbouring robots that it can detect. The second phase begins after the centralized host PC receives the relative location data sets from the swarm robots. However, in large swarms, computational scalability may become a concern if the topology estimation process depends entirely on a centralized computer. Thus, scalability is addressed herein through a divide-and-conquer approach that increases computational efficiency via grouping and stitching. ⁷⁵

One can note that the proposed algorithm is centralized in that all collected data is fused at a central computer to obtain an optimal swarm-topology estimate. The distributed portion of the method, on the other hand, is in data collection and initial interpretation, which is performed individually by each robot. Furthermore, all information is acquired from individual robots, and the central system cannot externally observe the swarm (i.e. there are no overhead sensors monitoring the environment in which the swarm is operating).

Phase I: Distributed relative localization

Relative (distributed) localization by an mROBerTO is carried out by measuring the proximities and bearings of nearby robots via its swarm-sensing module. The inclusion of the ATmega328P microcontroller within the swarm-sensing module provides mROBerTO with the unique feature of dedicated processing for localization. This allows it to acquire both proximity and bearing information without adding to the computational load of the main processing unit.

Determining the proximity and bearing to neighbouring robots begins when the IR emitters on mROBerTOs send out modulated signals through PWM. The signals are encoded with the robots’ unique IDs such that receiving robots can differentiate between signals received from different robots. The signals received by IR receivers are passed on to the ATmega328P microcontroller and demodulated to identify the respective robots emitting the signals. Once the IR signals are demodulated, the raw IR amplitudes for each nearby robot are normalized and summed

a_{i} = \sum_{k = 1}^{6} \frac{{IR}_{i k}}{{IR}_{max i k}}

where a_i is the normalized and summed IR amplitude value for the ith robot, IR _ik is the IR amplitude reading value for the ith robot and the kth IR detector, and IR_maxik is the maximum IR amplitude value recorded during offline calibration. a_i values are converted into proximity measurements according to a conversion function obtained during offline calibration.

Each mROBerTO determines the bearing of a nearby robot using the normalized IR amplitudes from each IR detector as the six wide-viewing angle (120°) IR detectors are configured for an all-around coverage. The normalized IR amplitudes from these six IR detectors are weighted to determine at which angle the signal was the strongest and estimate the bearing towards the neighbouring robot⁷⁴

\hat{φ_{i}} = arctan (\frac{\sum_{k = 1}^{6} ρ_{i k} sin (β_{k})}{\sum_{k = 1}^{6} ρ_{i k} cos (β_{k})})

where β_k is the angle between the robot’s heading and the kth sensor, and ${\hat{φ}}_{i}$ is the bearing estimate for the ith robot with respect to the estimating robot’s heading. ρ_ik is the scaled IR intensity reading of the ith robot from the kth sensor

ρ_{i k} = \frac{{IR}_{i k}}{{IR}_{max i k}}

Figure 4 shows two representative data sets for a 14-robot swarm example, where each plot presents the neighbouring robots detected. One must note that relative location-data sets, acquired from individual robots, would be restricted by the accuracy and detection radii of the IR emitters and receivers on the individual robots. Figure 4(a), for example, shows the relative locations of Robots 3, 4, 7 and 8, as detected by Robot 1. All other robots are not detectable by Robot 1. Similarly, Figure 4(b) shows the relative locations of Robots 3 and 4, as detected by Robot 2. All other robots are not detectable by Robot 2. Following this process, 14 (partial) data sets are obtained, 1 per every robot in the swarm.

Figure 4.

Visual representation of two simulated relative robot location data sets: (a) Robot 1 and (b) Robot 2.

Phase II: Swarm-topology estimation

As noted above, the proposed swarm-topology estimation method consists of two phases: (Phase I) distributed relative localization, through data acquisition from the swarm robots and, subsequent, (Phase II) global swarm-topology estimation, via a central computer. The three operations within Phase II are grouping, group-topology estimation and stitching. These were formulated similar to the three fundamental steps of divide-and-conquer approaches reported in the literature (divide, solve, merge).⁷⁶ In grouping, the robots are first divided into similarly sized sets based on robot visibility. After grouping, sub-topology estimation is performed for each group. Lastly, the central computer carries out stitching, in which the sub-topologies of all groups are combined into one global swarm topology.

Grouping

During this stage, the robots are combined into comparably sized sets through a grouping process. The approach employed is similar to the sensor-node clustering solutions reported in the literature for wireless sensor networks (refer to the work of Mahdi et al.,⁷⁷ Niu et al.⁷⁸ and Abdellatief et al.⁷⁹). Grouping must ensure that the subsets contain overlapping robots to allow for the final stitching stage of swarm-topology estimation.

As an example, Figure 5 continues the 14-robot swarm case discussed above, where the robots are combined into three groups. In this example, Robots 2 and 3 are present in both Groups A and B, and Robots 7 and 8 are present in both Groups A and C, respectively, to allow for stitching.

Figure 5.

Grouping of data sets.

Group-topology estimation

After grouping, sub-topology estimation (for each group) is carried out to fuse partial swarm-topology estimation data acquired from individual robots to determine the complete set of robot locations in the group. The method is novel in that it only requires partial location data sets acquired from individual robots to perform a complete swarm-topology estimation. In particular, the method performs swarm-topology estimation without any global position knowledge.

In order to fuse relative-location data, individual reference frames need to be transformed to positions and orientations in a common global reference frame. Namely, all data sets need to be superimposed and manipulated (translated and rotated), such that all respective robot data points are clustered to minimize distances between observed data points for every robot (e.g. all observations of Robot 1 should to be clustered together).

The clustering process is carried out sequentially and iteratively. Our approach is similar to ones proposed in the literature for 3D point-cloud registration⁸⁰ and template matching for object recognition.⁸¹

For example, for Group A in Figure 5 – Robots {1, 2, 3, 4, 7, 8}, let us choose Robot 1 as the reference, the left figure in Figure 6. Next, let us superimpose and manipulate the data sets for Robots 1 and 2, the centre figure in Figure 6, followed by the superimposition and manipulation of the data set for Robot 3 on this combined 1–2 data set, to yield 1–2–3, the right figure in Figure 6. The process continues until we achieve the superimposition of all the six-robot data sets in Group A. Once this initial superimposition is obtained, the process is repeated. Namely, Robot 1 data set is retransformed and manipulated to better fit data (post superimposition) from Robots 2, 3, 4, 7, 8 and so on. The process continues until a convergence criterion is met (i.e. until no further improvements can be made) and the optimal superimposition of data sets is obtained.

Figure 6.

Incremental superimposition and manipulation of the data sets in Figure 4.

Transformation of data sets

Formally, the problem of determining the optimal transform for a single data set is defined as follows: Let r_ij be the proximity of Robot j to Robot i, as observed by Robot i, and θ_ij be the bearing of Robot j in the local reference frame of Robot i, then the polar coordinates (r_ij , θ_ij ) denote the location of Robot j as observed by Robot i. The collection of all (r_ij , θ_ij ) for a given i is called the data set of Robot i and consists of all observations of other robots made by Robot i.

Let the transformation of data set i, from the local reference frame to the common global reference frame, be defined by a rotation of the data set, by α_i , about the local reference frame origin, and a subsequent translation, by (x_i , y_i ), in the x and y directions, respectively. Then, given the transformation parameters of the Robot i data set, (x_i , y_i , α_i ), the Cartesian coordinates of Robot j as observed by Robot i in the common global reference frame, X _ij are

X_{i j} = [\begin{matrix} r_{i j} cos (θ_{i j} + α_{i}) + x_{i} \\ r_{i j} sin (θ_{i j} + α_{i}) + y_{i} \end{matrix}]

Superimposition of data sets

The set of all data sets after transformation is referred to herein as superimposition. Our approach, to fuse all relative location data, is similar to the one reported in the literature for fusing multiple 3D point clouds.⁸² Namely, in order to fuse the relative-location data, transformation parameters for individual robot data sets are optimized sequentially to improve the superimposition. At each optimization step, a single set of transformation parameters is selected for optimization, leaving all others fixed. Optimal transformations are the ones that minimize the distances between observed data points for every robot. Namely, the transformation parameters of Robot i are optimized to minimize the maximum distance between the coordinates of a robot as observed by Robot i and the coordinates of the same robot as observed by all other robots

ϵ_{i} = max_{j, k} ||X_{i j} - X_{k j}||

where X_ij represents the Cartesian coordinates of Robot j in the global reference frame as observed by Robot i, X _kj represents the Cartesian coordinates of Robot j in the global reference frame as observed by Robot k and ||⋅|| denotes the Euclidean norm.

As an example for superimposition, let us consider Group A robots of the 14-robot swarm given in Figure 5, where the above proposed optimization is sequentially carried out, always manipulating one data set at a time while keeping the others fixed. The optimal superimposition of the six data sets is shown in Figure 7(a). Then, the estimated robot positions are calculated by determining the mean positions of all observations for the respective robots in the common global reference frame (see Figure 7(b)).

Figure 7.

The final estimate of sub-topology for Group (a) The optimal superimposition and (b) the final estimate of sub-topology for Group A after determining the mean positions of all observations.

The swarm-topology estimation process is repeated for every group of robots in the swarm. In our example, in Figure 5, for Groups A, B and C, the three sub-topologies obtained are shown in Figure 8.

Figure 8.

Estimated swarm sub-topologies of Groups (a) A, (b) B and (c) C.

Stitching

After obtaining the sub-topologies for all the groups of robots, the global swarm topology is obtained by stitching these sub-topologies together, which is similar to the clustering process described above. Namely, the group topologies are superimposed in a way that minimizes cluster sizes of overlapping robots. Our optimization procedure is similar to the one described in the work of Takimoto et al.,⁸² as discussed above.

As an example of stitching, the sub-topologies shown in Figure 8 were superimposed and optimized to yield a global (entire) swarm-topology estimate, as shown in Figure 9.

Figure 9.

Estimated entire swarm topology.

Experiments

In our previous work, reported in the work of Kim et al.^27,28 and Drisdelle et al.²⁹, mROBerTO was directly compared to the two best robots in the field, the Kilobot and TinyTeRP, and was determined to be clearly superior in locomotion, sensing and processing performance. Thus, the experiments presented in this section focus only on validating the global swarm-topology estimation method proposed in this article. The first subsection below presents results regarding distributed relative localization (i.e. Phase I), followed by global swarm-topology estimation (i.e. Phase II) in the next subsection, respectively. We also present an experiment that demonstrates the proposed method’s application to HSI scenarios.

Phase I: Distributed relative localization

In order to illustrate the distributed relative localization performance of mROBerTO, in all experiments, the robots were placed in known topologies and allowed to localize other robots in their vicinity. The localization results were, then, compared to the true positions of the robots to assess localization accuracy.

An example

Figure 10 shows the example (true) swarm configuration with (the maximum available number of) nine physical robots. Figure 11, in turn, shows the nine sets of localization data acquired through the swarm-sensing modules of the mROBerTOs – one for each robot.

Figure 10.

An example swarm configuration used for relative localization experiments.

Figure 11.

Visual representation of acquired nine relative robot location data sets for the configuration shown in Figure 10.

Phase II: Global swarm-topology estimation

The proposed global swarm-topology estimation method consists of two phases: (I) distributed relative localization, and (II) global swarm-topology estimation (see Figure 3). As discussed above, the first phase is carried out using the on-board processing and sensing capabilities of mROBerTOs. The second phase begins after the centralized host PC receives the relative location data sets from the swarm robots. The experiments presented in this subsection focus on Phase II.

Group-topology estimation

In grouping, the robots are first divided into similarly sized sets based on robot visibility (i.e. robots that detect the same neighbouring robots would likely be grouped together). After grouping, sub-topology estimation is performed for each group.

Below, we first present sub-topology estimation results for several experiments that utilize our nine (physical) mROBerTOs. Next, we expand the swarm to 30 robots by including a further 21 simulated robots and carry out sub-topology estimation for this larger group. Lastly, we discuss the arbitrary order of robot consideration during the superimposition step of the proposed iterative incremental process.

Examples with physical robots

For every scenario discussed below, the swarm of nine mROBerTO millirobots is initially arranged into a known topology. The robots are, then, allowed to communicate with each other using IR to locate other robots within their respective communication range. The data of relative robot proximities acquired by each robot are, subsequently, combined (i.e. superimposed) according to the proposed (group) topology-estimation algorithm. Figure 12 shows the final estimated group topology, for Example #1, using the data shown in Figure 11, where the estimate is also compared with respect to the corresponding true positions of the robots (in purple).

Figure 12.

The final estimated swarm topology for a set of nine physical robots shown in Figures 10 and 11.

Validation of the proposed topology-estimation algorithm is further shown here, using the nine physical mROBerTO units, for two additional different swarm-topologies. The topology shown in Figure 13(a), Example #2, has the robots arranged in a diamond shape. The topology shown in Figure 13(b), Example #3, has the robots distributed randomly. In both figures, the actual (true) robot positions are shown in purple, while the estimated robot positions are shown in green.

Figure 13.

Swarm-topology estimation: (a) diamond-shaped and (b) random-shaped.

Dissimilarity measure

From the experiments above, it is evident that the group topology can be successfully estimated for swarms of mROBerTOs via our proposed topology-estimation method. However, in order to quantitatively measure the dissimilarity between the actual (true) and measured (estimated) shapes, a topology signature was defined in our work as the polar coordinates of all robots with respect to one reference robot, in our examples chosen as Robot 1. Figure 14, as an example, shows the successful convergence of the average dissimilarity measure for the diamond topology shown in Figure 13(a).

Figure 14.

Average dissimilarity of the estimated swarm from desired diamond topology shown in Figure 13.

Table 1 presents the dissimilarity measure in terms of the normalized errors between the topology signatures of the actual (true) and measured (estimated) relative robot locations (r: proximity and θ: bearing) for three topologies. The minimum, maximum and average errors for each experiment are given. The normalization factor used was proportional to the radius of the swarm.

Table 1.

Topology-error data.

	Random #1 (Figure 12)	Diamond (Figure 13(a))	Random #2 (Figure 13(b))
Min. r error (%)	3	0	3
Avg. r error (%)	11	3	13
Max. r error (%)	38	6	34
Min. θ error (%)	0	3	0
Avg. θ error (%)	5	8	10
Max. θ error (%)	14	12	20

Min.: minimum; Avg. average; Max.: maximum; r: proximity; θ: bearing.

A larger scale group-topology estimation example

Validation of the proposed method’s ability to estimate the topology of a larger scale swarm is shown in this subsection for a group of 30 simulated robots. The acquired localization data for the non-physical robots included noise modelled to emulate the characteristics of real-world sensing conditions²⁸ for the mROBerTOs. The true and the estimated topologies for the swarm considered are shown in Figure 15.

Figure 15.

The true and estimated group topologies for the larger scale estimation experiment.

The dissimilarity measure for this case was computed to assess the estimation accuracy (refer Table 2). The results are comparable to those obtained for the (physical) nine-robot topology-estimation experiments. Namely, estimation accuracy is not tangibly compromised by increasing the group size.

Table 2.

Topology-error data for the large-scale group-topology estimation experiment.

	Large-scale group
Min. r error (%)	0
Avg. r error (%)	6
Max. r error (%)	30
Min. θ error (%)	1
Avg. θ error (%)	8
Max. θ error (%)	18

Min.: minimum; Avg. average; Max.: maximum; r: proximity; θ: bearing.

Order of superimposition evaluation

The order of robots in the superimposition step of the proposed iterative incremental process can be arbitrary, though different orders would, as expected, yield different results. In order to illustrate the (lack of) impact of superimposition sequence on the final estimated topology, the outcomes of five different superimposition sequences are shown in Figure 16.

Figure 16.

Swarm-topology estimation, for Group A, using different superimposition sequences: (a) a 0.1% improvement threshold stopping condition and (b) 1000-iteration optimization.

Experiments were first run until less than 0.1% improvement in the objective function was observed per iteration (see Figure 16(a)). Then, the optimization algorithm was re-run for 1000 iterations to illustrate convergence (see Figure 16(b)). The results demonstrate that all sequences result in topologies that are nearly identical, which would be sufficient for a human supervisor in making decisions based on the estimated swarm topology.

Stitching

As noted above, the computational scalability of the topology-estimation algorithm proposed in this article is achieved through a divide-and-conquer approach. Namely, first, the swarm is divided into smaller groups, whose individual topologies are determined in parallel. Subsequently, a central unit combines these estimates into a global swarm-topology estimate via a mathematical operation, referred to as stitching in this article. This approach leverages the parallel computing ability of swarms to distribute the computational load across groups.

As a stitching example, a swarm of 400 simulated robots were considered. The robots were grouped into 24 different sets (refer Table 3), and the group-topologies were estimated. Subsequently, these were stitched to form the overall swarm-topology estimate. Figure 17(a) to (c) shows the results of the first three sequential superimposition steps, and Figure 17(d) and (e) shows the last two, respectively. The final swarm-topology estimation is shown in Figure 18.

Table 3.

Group member lists.

Group #	Group member list
1	{8, 25, 38, 44, 56, 62, 68, 85, 86, 106, 128, 142, 167, 191, 200, 212, 213, 246, 274, 277, 287, 305, 306, 309, 371}
2	{6, 9, 13, 50, 60, 65, 77, 95, 128, 132, 142, 162, 167, 168, 183, 223, 260, 293, 350, 369, 372}
⋮	⋮
23	{1, 31, 35, 58, 72, 129, 135, 145, 149, 265, 267, 271, 284, 298, 326, 332, 334, 342, 346, 356, 379, 393, 396}
24	{12, 49, 54, 58, 99, 146, 163, 190, 206, 241, 276, 288, 314, 330, 332, 335, 339, 341, 351, 362, 382, 386}

Figure 17.

Sequential superimposition: (a) one group topology, (b) two group topologies and (c) three group topologies, and the last two superimpositions with (d) 23 group topologies and (e) 24 group topologies.

Figure 18.

The final swarm-topology estimation for a 400-robot swarm.

Human–swarm interaction

The results of an additional experiment are included herein to demonstrate the proposed method’s use in HSI, where a swarm of nine physical robots (in the field) were asked to change their topology through input from a remote supervisor. Specifically, the swarm with an initial random topology (see Figure 19(a)) was instructed to reconfigure itself into a diamond shape centred about Robot 1.

Figure 19.

The evolution of the robot swarm over time from a random-shaped to a diamond-shaped topology.

As noted above, the remote supervisor could not directly observe the physical swarm and only had access to the estimated topology of the swarm through a graphical user interface. Figure 19(b) to (e) shows the evolution of the swarm topology, with progress from left to right. The middle row indicates the true robot positions (corresponding to the photos in the row above), while the bottom row indicates estimated swarm topologies. Swarm-topology estimation was performed at every iteration in order to provide the supervisor with up-to-date information regarding the latest swarm state.

Comparison to other topology estimation and localization methods

As noted above, the proposed method calculates a detailed swarm topology estimate using the relative positions of all the robots. This contrasts with other swarm-topology estimation methods,^72,73 which typically use summary statistics regarding the swarm. Furthermore, the proposed method achieves relative localization for topology estimation without the use of anchors or need for robot motion, as is typical in most other methods.^{60

–71} Use of anchors, for example, would need the designation of some of the robots as such, requiring design modifications. Similarly, incremental movement of robots would consume valuable time.

Several methods that address topology estimation in a manner similar to our proposed method can be found in the wireless sensor network literature.^83
–85 In these cases, sensors do not move, and a map of relative positions is estimated. The most pertinent of these consider the angle of arrival of signals as well as signal strength (as a proxy measurement of range) to estimate sensor positions.^86,87 However, as in swarm-topology estimation, these methods also, typically, use anchors.

The proposed method, on the other hand, fuses incomplete data sets acquired from multiple static robots without anchors. Namely, data fusion is uniquely performed using superimposition of data and clustering of observations to obtain an estimate of the complete swarm topology. Furthermore, the proposed algorithm offloads some of the processing tasks to individual millirobots, such that the central computer carries out only high-level optimization. This contrasts with other approaches in which either raw data are processed entirely within a central computer to obtain location estimates or (limited) distributed swarm-topology estimation is carried out on a per-robot basis.

In regards to localization, mROBerTO’s swarm-sensing module achieves accuracy comparable to or better than those reported in the literature while allowing the robots to remain stationary, thus, improving the efficiency of the robots’ operation. The specific analysis reported in our earlier article²⁸ showed that the module’s bearing measurements had an average error of up to 10° and an average proximity (range) error of up to 5% of its maximum range. In comparison, the results presented in the work of Cornejo and Nagpal⁶¹ had a mean squared localization error of up to, approximately, 5% of the workspace size, a root mean squared localization error of approximately 7%, depending on the noise.

A more direct comparison of our results was also made with those presented in the work of Mao et al.,⁶² which reported an average bearing error of approximately 5° and an average range measurement error of up to approximately 4% of its maximum range. However, the method in the work of Mao et al.⁶² utilizes two robots in a cooperative manner in order to achieve the above-mentioned accuracy while mROBerTOs achieve similar results independently.

Conclusions

This article presents the design of a novel high-performance, modular millirobot, the mROBerTO. The robot design uses only commercially available components, has a minimal footprint and achieves reliable locomotion while having uncompromised sensory, communication and processing capabilities. mROBerTO is capable of IR-based proximity and bearing localization, has Bluetooth Smart and ANT+ communication capabilities and uses a 32-bit ARM Cortex-M0 central processing unit, all of which are unique to its design. These capabilities make mROBerTO a good candidate for use in complex swarm-behaviour studies, including the ability to localize the overall swarm for HSI testing.

In the above-mentioned regard, extensive experiments, utilizing physical and simulated robots, indeed demonstrated the effectiveness of the proposed global swarm-topology estimation method, including its upward scalability. Consequently, it is anticipated that our future work will aim to utilize the mROBerTOs for HSI experimentation, once sufficient progress is made on the latter front. Parallel work will also focus on improving the mROBerTO’s hardware/software. This will include upgrading the robot’s processing, sensing and locomotion capabilities.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Natural Sciences and Engineering Research Council of Canada and the Canada Research Chairs Program.

ORCID iD

Zendai Kashino

References

Lopes

Leal

Dodd

, et al. Application of supervisory control theory to swarms of e-puck and kilobot robots. In: Swarm intelligence proceedings 9th international conference swarm intelligence (eds Dorigo

Birattari

Garnier

, et al. ),. Brussels, Belgium, 10–12 September 2014, pp. 62–73. Basel; Charm: Springer.

Correll

Rutishauser

Martinoli

Comparing coordination schemes for miniature robotic swarms: a case study in boundary coverage of regular structures. In: Khatib

Kumar

Rus

(eds) Experimental robotics. Heidelberg; Berlin: Springer, 2008, pp. 471–480.

Fyler

Sullivan

Raptis

. Distributed object manipulation using a mobile multi-agent system. In: Proceedings of IEEE international conference technologies for practical robot applications (TePRA), Woburn, USA, 11–12 May 2015. Piscataway, New Jersey: IEEE.

Bergbreiter

. Effective and efficient locomotion for millimeter-sized microrobots. In: Proceedings of IEEE/RSJ international conference intelligent robots and systems, Nice, France, 22–26 September 2008, pp. 4030–4035. Piscataway, New Jersey: IEEE.

Bakhtari

Benhabib

. An active vision system for multitarget surveillance in dynamic environments. IEEE Trans Syst Man Cybern B (Cybern) 2007; 37: 190–198.

Bakhtari

Naish

Eskandari

, et al. Active-vision-based multisensor surveillance – an implementation. IEEE Trans Syst Man Cybern C (Appl Rev) 2006; 36: 668–680.

Kashino

Vilela

Kim

, et al. An adaptive static-sensor network deployment strategy for detecting mobile targets. In: IEEE international symposium on safety, security, and rescue robotics, Lausanne, Switzerland, 23–27 October 2016, pp. 1–8. Piscataway, New Jersey: IEEE.

Kashino

Kim

Nejat

, et al. Spatiotemporal adaptive optimization of a static-sensor network via a non-parametric estimation of target location likelihood. IEEE Sensors J 2017; 17: 1479–1492.

Macwan

Nejat

Benhabib

. Optimal deployment of robotic teams for autonomous wilderness search and rescue. In: IEEE/RSJ international conference intelligent robots and systems (eds Amato

Chen

Luca

), San Francisco, CA, 25–30 September 2011, pp. 4544–4549. Piscataway, New Jersey: IEEE.

10.

Macwan

Vilela

Nejat

, et al. A multirobot path-planning strategy for autonomous wilderness search and rescue. IEEE Trans Cybern 2015; 45: 1784–1797.

11.

Macwan

Nejat

Benhabib

. Target-motion prediction for robotic search and rescue in wilderness environments. IEEE Trans Syst Man Cybern B (Cybern) 2011; 41: 1287–1298.

12.

Fearing

. Challenges for efffective millirobots. In: Proceedings of international symposium on MicroNanoMechanical and human science, Nagoya, Japan, 5–8 November 2006, pp. 1–5. Piscataway, New Jersey: IEEE.

13.

Zhang

Nejat

Guo

, et al. A novel 3D sensory system for robot-assisted mapping of cluttered urban search and rescue environments. Intell Serv Robotics 2011; 4: 119–134.

14.

Hong

Igharoro

Liu

, et al. Investigating human-robot teams for learning-based semi-autonomous control in urban search and rescue environments. J Intell Robot Syst. Epub ahead of print 9 August 2018. DOI: 10.1007/s10846-018-0899-0.

15.

Mahoney

Abbott

. Five-degree-of-freedom manipulation of an untethered magnetic device in fluid using a single permanent magnet with application in stomach capsule endoscopy. Int J Robot Res 2015; 35(1-3): 129–147.

16.

Yim

Gultepe

Gracias

, et al. Biopsy using a magnetic capsule endoscope carrying, releasing, and retrieving untethered microgrippers. IEEE Trans Biomed Eng 2014; 61(2): 513–521.

17.

Vartholomeos

Vlachos

Papadopoulos

. Analysis and motion control of a centrifugal-force microrobotic platform. IEEE Trans Autom Sci Eng 2013; 10(3): 545–553.

18.

El-Moukaddem

Torng

Xing

, et al. Mobile relay configuration in data-intensive wireless sensor networks. IEEE Trans Mob Comput 2013; 12(2): 261–273.

19.

Lembke

Kietlinski

Golanski

, et al. RoboMote: Mobile autonomous hardware platform for wireless ad-hoc sensor networks. In: Proceedings of IEEE international symposium on industrial electronics, Gdansk, Poland, 27–30 June 2011, pp. 940–944. Piscataway, New Jersey: IEEE.

20.

Yim

Kim

. Origami-inspired printable tele-micromanipulation system. In: Proceedings of IEEE international conference robot and automation, Seattle, WA, 26–30 May 2015, pp. 2704–2709. Piscataway, New Jersey: IEEE.

21.

Bruhwiler

Goldberg

Doshi

, et al. Feedback control of a legged microrobot with on-board sensing. In: Proceedings of IEEE/RSJ international conference intelligent robots and systems (eds Burgard

Arai

, et al.), Hamburg, Germany, 28 September–2 October 2015, pp. 5727–5733. Piscataway, New Jersey: IEEE.

22.

Haldane

Fearing

. Running beyond the bio-inspired regime. In: Proceedings of IEEE international conference robotics and automation, Seattle, WA, 26–30 May 2015, pp. 4539–4546. Piscataway, New Jersey: IEEE.

23.

Christensen

Hawkes

Suresh

, et al. μTugs: enabling microrobots to deliver macro forces with controllable adhesives. In: Proceedings of IEEE international conference robotics and automation, Seattle, WA, 26–30 May 2015, pp. 4048–4055. Piscataway, New Jersey: IEEE.

24.

Kennedy

Eberhart

Shi

. Swarm intelligence. San Francisco: Morgan Kaufmann, 2001.

25.

Arbuckle

Requicha

AAG

. Self-assembly and self-repair of arbitrary shapes by a swarm of reactive robots: algorithms and simulations. Auton Robots 2010; 28(2): 197–211.

26.

Nunnally

Walker

Kolling

, et al. Human influence of robotic swarms with bandwidth and localisation issues. In: Proceedings of IEEE international conference systems, man, and cybernetics, Seoul, South Korea, 14–17 October 2012, pp. 333–338. Piscataway, New Jersey: IEEE.

27.

Kim

Colaco

Kashino

, et al. mROBerTO: a modular millirobot for swarm-behavior studies. In: Proceedings of IEEE/RSJ international conference intelligent robots and systems, Daejeon, Korea, 9–14 October 2016, pp. 2109–2114. Piscataway, New Jersey: IEEE.

28.

Kim

Kashino

Colaco

, et al. Design and implementation of a millirobot for swarm studies – mROBerTO. Robotica 2018; 36: 1591–1612.

29.

Drisdelle

Kashino

Pineros

, et al. Motion control of a wheeled millirobot. In: Proceedings of the international conference control dynamic systems robotics, Toronto, Canada, 21–23 August 2017. Orléans, Ontario, Canada: Avestia.

30.

Pickem

Lee

Egerstedt

. The GRITSBot in its natural habitat – a multi-robot testbed. In: Proceedings of IEEE international conference robotics automation, Seattle, WA, 26–30 May 2015, pp. 4062–4067. Piscataway, New Jersey: IEEE.

31.

Jang

Villalba

Paley

, et al. RSSI-based rendezvous on the tiny terrestrial robotic platform (TinyTeRP). Report, Institute of Systems Research, University of Maryland, College Park, USA, 2013.

32.

Sabelhaus

Mirsky

Hill

, et al. TinyTeRP: a tiny terrestrial robotic platform with modular sensing. In: Proceedings of IEEE international conference robotics automation, Karlsruhe, Germany, 6–10 May 2013, pp. 2600–2605. Piscataway, New Jersey: IEEE.

33.

Kettler

Szymanski

Wörn

. The Wanda robot and its development system for swarm algorithms. In: Proceedings of advances autonomous mini robots symposium (eds Rückert

Joaquin

Felix

), Bielefeld, Germany, 23–25 May 2011, pp. 133–146. Heidelberg; Berlin: Springer.

34.

Arvin

Samsudin

. Development of a miniature robot for swarm robotic application. Int J Comput Electr Eng 2009; 1(4): 436–442.

35.

Arvin

Doraisamy

Samsudin

, et al. Self-localisation of swarm robots based on voice signal acquisition. In: International conference on computer and communication engineering (ICCCE’10), Kuala Lumpur, Malaysia, 11–12 May, 2010, pp. 1–5. Piscataway, New Jersey: IEEE.

36.

Kornienko

. IR-based communication and perception in microrobotic swarms. eprint arXiv:1109.3617 , 2011.

37.

Caprari

Siegwart

. Mobile micro-robots ready to use: Alice. In: Proceedings of IEEE/RSJ International Conference Intelligent Robots Systems, Edmonton, Canada, 2–6 August 2005, pp. 3295–3300. Piscataway, New Jersey: IEEE.

38.

Rubenstein

Ahler

Hoff

, et al. Kilobot: a low cost robot with scalable operations designed for collective behaviours. Robot Auton Syst 2014; 62(7): 966–975.

39.

Arvin

Murray

Zhang

, et al. Colias: an autonomous micro robot for swarm robotic applications. Int J Adv Robot Syst 2014; 11(7): 1–10.

40.

Liu

Winfield

AFT

. Open-hardware e-puck Linux extension board for experimental swarm robotics research. Microprocess Microsyst 2011; 35(1): 60–67.

41.

Gross

Bonani

Mondada

, et al. Autonomous self-assembly in swarm-bots. IEEE Trans Robot 2006; 22(6): 1115–1130.

42.

McLurkin

McMullen

Robbins

, et al. A robot system design for low-cost multi-robot manipulation. In: Proceedings of IEEE/RSJ International Conference Intelligent Robots Systems (eds Burgard

Arai

, et al.), Chicago, IL, 14–18 September 2014, pp. 912–918. Piscataway, New Jersey: IEEE.

43.

Habibi

Kingston

Xie

, et al. Distributed centroid estimation and motion controllers for collective transport by multi-robot systems. In: Proceedings of IEEE International Conference Robotics Automation, Seattle, WA, 26–30 May 2015, pp. 1282–1288. Piscataway, New Jersey: IEEE.

44.

GCtronic. Mobile robot products, http://www.gctronic.com/products.php (2012, accessed 17 February 2016).

45.

K-Team Corporation. K-Team mobile robot products, http://www.k-team.com/mobile-robotics-products (2011, accessed 17 February 2016).

46.

Barca

Sekercioglu

. Swarm robotics reviewed. Robotica 2013; 31(3): 345–359.

47.

Mondada

Pettinaro

Guignard

, et al. Swarm-Bot: a new distributed robotic concept. Auton Robots 2004; 17(2-3): 193–221.

48.

Todor

Darabos

. Simultaneous localisation and mapping with particle swarm localisation. In: Proceedings of IEEE Intelligent Data Acquisition Advances Computing Systems: Technology and Applications, Sofia, Bulgaria, 5–7 September 2005, pp. 216–221. Piscataway, New Jersey: IEEE.

49.

Bashyal

Venayagamoorthy

. Human swarm interaction for radiation source search and localisation. In: Proceedings of IEEE Swarm Intelligence Symposium, St. Louis, MO, 21–23 September 2008, pp. 1–8. Piscataway, New Jersey: IEEE.

50.

Rodrigues

Duarte

Figueiró

, et al.

Overcoming limited onboard sensing in swarm robotics through local communication. In: Nguyen N, Kowalczyk R, Duval B, et al. (eds)

Transactions on Computational Collective Intelligence XX. Cham: Springer, 2015, pp. 201–223.

51.

Nagi

Ngo

Gambardella

, et al. Wisdom of the swarm for cooperative decision-making in human-swarm interaction. In: Proceedings of IEEE International Conference Robotics Automation, Seattle, WA, 26–30 May 2015, pp. 1802–1808. Piscataway, New Jersey: IEEE.

52.

Şahin

Spears

(eds) Swarm robotics. Heidelberg; Berlin: Springer, 2005.

53.

Fredslund

Mataric

. A general algorithm for robot formations using local sensing and minimal communication. IEEE Trans Robot Autom 2002; 18(5): 837–846.

54.

Pham

, et al. Simultaneous localisation and mapping: swarm robot mutual localisation and sonar arc bidirectional carving mapping. Proc Inst Mech Eng C: J Mech Eng Sci 2011; 225(3): 733–744.

55.

Kolling

Walker

Chakraborty

, et al. Human interaction with robot swarms: a survey. IEEE Trans Hum-Mach Syst 2016; 46(1): 9–26.

56.

Vasile

Pavel

Buiu

. Integrating human swarm interaction in a distributed robotic control system. In: Proceedings of IEEE International Conference Automation Science Engineering, Trieste, Italy, 24–27 August 2011, pp. 743–748. Piscataway, New Jersey: IEEE.

57.

Millard

Hilder

Timmis

, et al. A low-cost real-time tracking infrastructure for ground-based robot swarms. In: Dorigo

Birattari

Garnier

(eds) Swarm Intelligence Proceedings International Conference Swarm Intelligence, Brussels, Belgium, 10–12 September 2014, p. 278. Basel; Charm: Springer.

58.

Gilles

Sharma

Ferenc

, et al. Robot swarming over the Internet. In: Proceedings American Control Conference, Falmont Queen Elizabeth, Canada, 27–29 June 2012, pp. 6065–6070. Piscataway, New Jersey: IEEE.

59.

Ekberg

. Swarm-intelligent localisation. eprint diva2:233958 [Internet], 2009, [cited 13 January 2017], http://uu.diva-portal.org/smash/record.jsf?pid=diva2%3A233958 (accessed 13 January 2017).

60.

Strader

Gross

, et al. Cooperative relative localisation for moving UAVs with single link range measurements. In: Proceedings of IEEE/ION position, location and navigation symposium, Savannah, GA, 11–14 April 2016, pp. 336–343. Piscataway, New Jersey: IEEE.

61.

Cornejo

Nagpal

. Distributed range-based relative localization of robot swarms. In: Akin

Amato

Isler

, et al. (eds) Algorithmic found robot XI. Cham: Springer International Publishing, 2015, pp. 91–107.

62.

Mao

Chen

, et al. Relative localisation method of multiple micro robots based on simple sensors. Int J Adv Robot Syst 2013; 10: 128.

63.

Coppola

McGuire

Scheper

KYW

, et al. Onboard Bluetooth-based relative localisation for collision avoidance in micro air vehicle swarms. Auton Robot 2018; 42(8): 1787–1805.

64.

Shariati

Mohta

Taylor

. Recovering relative orientation and scale from visual odometry and ranging radio measurements. In: Proceedings of IEEE/RSJ international conference intelligent robots systems, Daejeon, South Korea, 9–14 October 2016, pp. 3627–3633. IEEE.

65.

Sun

Xiao

Cabrera-Mora1

. Robot localisation and energy-efficient wireless communications by multiple antennas. In: Proceedings IEEE/RSJ international conference intelligent robots systems, St. Louis, MO, 10–15 October 2009, pp. 377–381. IEEE.

66.

Cheng

Han

Zhang

, et al. A single-mobile-anchor based distributed localisation scheme for sensor networks. In: Proceedings of Chinese control conference, Chengdu, P.R. China, 27–29 July 2016, pp. 8026–8031. IEEE.

67.

Kumar

Rai

. An energy efficient and optimized load balanced localisation method using CDS with one-hop neighbourhood and genetic algorithm in WSNs. J Netw Comput Appl 2017; 78: 73–82.

68.

Cheng

Vandenberghe

Yao

. Distributed algorithm for node localisation in wireless ad-hoc networks. ACM Trans Sens Netw 2009; 6(1): 8.

69.

de Sá

Nedjah

de Macedo Mourelle

. Distributed efficient localisation in swarm robotic systems using swarm intelligence algorithms. Neurocomputing 2016; 172: 322–336.

70.

Ekberg

Ngai

ECH

. A distributed swarm-intelligent localisation for sensor networks with mobile nodes. In: Proceedings of wireless communications and mobile computing conference (IWCMC), 2011 7th international, Istanbul, Turkey, 4–8 July 2011, pp. 83–88. IEEE.

71.

de Sá

Nedjah

de Macedo Mourelle

. Genetic and backtracking search optimisation algorithms applied to localisation problems. Int J Innov Comput Appl 2015; 6(3-4): 223–228.

72.

Lantao

Fine

Shell

, et al. Approximate characterization of multi-robot swarm “shapes” in sublinear-time. In: IEEE international conference robotics automations, Shanghai, China, 9–13 May 2011, pp. 2886–2891. IEEE.

73.

Freeman

Peng

Lynch

. Distributed estimation and control of swarm formation statistics. In: American control conference, Minneapolis, MN, 14–16 June 2006, pp. 749–755. IEEE.

74.

YouTube. mROBerTO (milli-ROBot-TOronto) for Swarm Robotics , https://www.youtube.com/watch?v=H-kuOcyjWsQ (2016, accessed 15 June 2019).

75.

Laflin

Anderson

Khan

, et al. New and extended applications of the divide-and-conquer algorithm for multibody dynamics. J Comput Nonlinear Dyn 2014; 9. Epub ahead of print 1 October 2014. DOI: 10.1115/1.4027869.

76.

Stout

. Supporting divide-and-conquer algorithms for image processing. J Parallel Distrib Comput 1987; 4: 95–115.

77.

Mahdi

Abdul Wahab

Idna Idris

, et al. A comparison study on node clustering techniques used in target tracking WSNs for efficient data aggregation. Wirel Commun Mob Comput 2016; 16(16): 2663–2676.

78.

Niu

d’Auriol

Lee

. General criteria-based clustering method for multi-node computing system. J Supercomput 2012; 61(3): 869–893.

79.

Abdellatief

Youness

Abdelkader

, et al. Global distributed clustering technique for randomly deployed wireless sensor networks. In: Proceedings of international computing engineering conference, Giza, Egypt, 28–29 December 2016, pp. 8–13. IEEE.

80.

Xin

. An improved ICP algorithm for point cloud registration. In: Proceedings of international conference computational and information science, Chengdu, China, 17–19 December 2010, pp. 565–568. IEEE.

81.

Pham

Jalovecky

Polasek

. Using template matching for object recognition in infrared video sequences. In: Proceedings of IEEE/AIAA digital avionics systems conference (ed Rossetti

), 2015, pp. 1–15. Piscataway, New Jersey: IEEE.

82.

Takimoto

Vogelaar

Ueda

, et al. 3D reconstruction using low precision scanner. IFAC Proc Vol 2013; 46: 239–244.

83.

Liu

Yin

Zhang

, et al. Range-based localization for sparse 3-D Sensor networks. IEEE Internet Things J 2019; 6: 753–764.

84.

Ukani

Thakkar

Parikh

. A range-based adaptive and collaborative localization for wireless sensor networks. In: Satapathy

Joshi

(eds) Information and communication technology for intelligent systems. Singapore: Springer, 2019, pp. 293–302.

85.

Jian-guo

Zhong-sheng

Ling

, et al. An improved range-based localization algorithm in wireless sensor network. In: Proceedings of international conference biomedical engineering information (eds Ding

Peng

Shi

, et al.), 2011, pp. 2157–2161. Piscataway, New Jersey: IEEE.

86.

Kułakowski

Vales-Alonso

Egea-López

, et al. Angle-of-arrival localization based on antenna arrays for wireless sensor networks. Comput Elec Eng 2010; 36: 1181–1186.

87.

Kotwal

Verma

Suryansh , et al. Region based collaborative angle of arrival localization for wireless sensor networks with maximum range information. In: Proceedings of international conference on computational intelligence and communication networks, Bhopal, India, 26–28 November 2010, pp. 301–307. IEEE.

A high-performance millirobot for swarm-behaviour studies: Swarm-topology estimation

Abstract

Keywords

Introduction

Millirobot designs

Swarm-localization and topology estimation

Problem statement

Overview of University of Toronto milli-robot design

The swarm-sensing module

Swarm-topology estimation

Phase I: Distributed relative localization

Phase II: Swarm-topology estimation

Grouping

Group-topology estimation

Transformation of data sets

Superimposition of data sets

Stitching

Experiments

Phase I: Distributed relative localization

An example

Phase II: Global swarm-topology estimation

Group-topology estimation

Examples with physical robots

Dissimilarity measure

A larger scale group-topology estimation example

Order of superimposition evaluation

Stitching

Human–swarm interaction

Comparison to other topology estimation and localization methods

Conclusions

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References