Friday, July 2, 2021

Visually appealing automated formations with multiple robots

RSS 2021: Robotics x Arts Workshop

Saurav Agarwal ( and Srinivas Akella

Humans have always looked up in the sky and observed patterns. We have joined the twinkling dots, formed shapes and given names to them. Children have pointed to stars and imagined moving them to form new shapes with the sky as their canvas. We have come a long way from observing patterns and creating marching band formations to now creating formations with thousands of drones in the sky. However, if the sky is our canvas, then there are additional questions that need to be answered. How large should the drawing be and where should we form them? Which robot should go where? We should let the algorithms handle these problems and let children do what they are best at: being creative.

Teams of robots often have to move from one formation to another as they perform exploration, coverage, and surveillance tasks. Such application scenarios are becoming increasingly common as the cost of robots continues to drop. Most work uses a single predefined goal formation for the team of robots or selects from a set of predefined formations. Such approaches do not exploit the additional flexibility for the goal formation that is often possible---the formation could be scaled or its location may be changed to optimize the objective function. While efficient algorithms for variable formations with fixed assignments exists, there is only limited prior work where both the assignment and the variable formation are considered simultaneously. This is precisely the gap that this work addresses.

In this work, we present algorithms to simultaneously compute the optimal assignments and formation parameters for a team of robots from a given initial formation to a variable goal formation. The shape of the goal formation is given, and its scale and location parameters must be optimized. We assume the robots are identical circles/spheres. We use the sum of squared travel distances as the objective function to be minimized. The algorithms ensure that the generated trajectories are collision free---the robots do not collide with one another. Moreover, all the robots start simultaneously and reach their respective goal positions simultaneously, resulting in a visually appealing formation of robots. We show that this assignment with variable goal formation problem can be transformed to a linear sum assignment problem (LSAP) with pseudo costs that we establish are independent of the formation parameters. The transformed problem can then be solved using the Hungarian algorithm. Thus the assignment problem with variable goal formations using this new approach has the same time complexity as the standard assignment problem with fixed goal formations.

The algorithms presented benefit an emerging novel application: the programming of large teams of mobile robots or UAVs to create animated light shows with LEDs mounted on the robots. Here the synchronized robot formations create visual images for entertainment. The quadrotor drones have LED lights that change color and intensity to create appealing 3D displays. The robots must be assigned goal locations and moved to them along generated collision-free trajectories. These algorithms would also benefit nanosatellite swarm formations requiring reconfiguration.

Another application domain these algorithms are designed to address is droplet-based lab-on-chip systems for point-of-care medical diagnostics. In these light-actuated digital microfluidic (LADM) systems, discrete droplets of chemicals are optically actuated using moving patterns of projected light to perform chemical reactions by repeatedly moving droplets to mixing formations. By modeling the droplets as robots, we can address the automated coordination of droplets on the LADM chip, including determining goal formations that can fit within specified regions of the chip.

Paper: Saurav Agarwal and Srinivas Akella, (2018), Simultaneous optimization of assignments and goal formations for multiple robots IEEE International Conference on Robotics and Automation, May 2018.

All info credited to the authors listed above.