Object Sorting and Planar Construction

This has been our group’s most active topic. We are interested in how a swarm of robots can manipulate objects of different types into segregated groups (object sorting) and how those groups can be pushed into desired shapes (planar construction).

A recent example on this topic is Mohammed Abdullhak’s paper on sorting with the help of buffered Voronoi cells [Abdullhak and Vardy, 2022]. Check out a live demo here.

This video accompanies the paper [Vardy, Vorobyev and Banzhaf, 2014].

Regarding the biological inspiration for this topic—social insects such as ants and bees manipulate resources in their environment to suit their needs. For example, ants sort their brood (i.e. ant babies) by size. They also cluster dead ants into groups. The interesting bit is that the ants achieve this without supervision and without consulting a “master plan”. We are interested in borrowing mechanisms for social insect sorting and construction for use in robotics.

Orbital Construction

Orbital construction (OC) is an algorithm that drives a swarm of simple robots to push objects into a desired shape. The shape is specified by a scalar field which plays a similar role to the pheromones used by social insects (e.g. termites and ants) when forming their sophisticated nest structures. Check out a live demo on SwarmJS.

OC was introduced in [Vardy, 2018]. M.Sc student Caroline Strickland then investigated the application of Reinforcement Learning to the problem of pushing objects into a desired shape. [Strickland, Churchill and Vardy, 2019]. We also developed a hardware realization of this algorithm [Vardy and Ibrahim, 2020].

Pattern Formation

For a team to collaborate more effectively it is often beneficial for its members to assume a formation. For example, a team of rescuers forming a line to quickly cover an area; a group of ploughs forming a wedge to level terrain. This project’s focus is on the development of bearing-only pattern formation algorithms which do not require robots to be uniquely identifiable to each other (i.e. they are anonymous). The use of anonymous, bearing-only inputs to the algorithm reduces the computational and sensory requirements of the robotic platform running the algorithm.

The video above accompanies the paper [Shiell and Vardy, 2016]. The robots used were adapted from those described in [Vardy and Shiell, 2016].

Robot Aggregation

Aggregation is a useful building block behaviour that can allow a swarm of robots to interact with each other or a user more easily. Previous work on swarm robot aggregation has assumed that the capabilities of individual robots are quite limited. We test whether incorporating odometry as an additional capability is helpful and make the argument that odometry is both realizable and biologically plausible.

The video above accompanies the paper [Vardy, 2016].

The microUSV Swarm

The microUSV is a small, open source unmanned surface vehicle (USV) designed as low cost marine robotics research platform for laboratory environments. Each unit costs approximately $500 Canadian dollars and measures 230mm x 89mm x 121mm making them ideal for swarm robotics research.

The design files, source code, BOM and other materials are hosted by the Open Science Framework.

Theoretical Analysis

In addition to the experimental approach, we have also investigated the application of computational complexity theory to certain problems in swarm robotics. In [Wareham and Vardy, 2018] we considered the design of controllers and environments in which robots are tasked with building some target structure. Two design problems were considered: (1) Designing the robot controllers (ContDes) and (2) Designing features in the environment to help guide construction (ContEnv). It turns out that both design problems are intractable if one wants to build arbitrary structures, not only in general but also relative to many combinations of restrictions on the controllers and the swarm operating environment (see table above). We also considered the general design problem for reactive robot controllers applied to arbitrary tasks and found situations in which the design problem was either tractable or intractable [Wareham and Vardy, 2018].

Visual Homing

Visual homing is the ability to return to a goal by comparing an image captured at the goal to the current image. It is believed to be a fundamental mechanism in the navigational capabilities of insects such as bees and ants. It is also useful for robotics as a means of moving between familiar places. Biologically plausible visual homing was the subject of Dr. Andrew Vardy’s Ph.D thesis.

The video above accompanies the paper [Vardy and Moeller, 2005].