by Daniel H. Stolfi and Carlos Kavka (Luxembourg Institute of Science and Technology)
Swarms of collaborative robots have been proposed for performing several complex tasks in scientific literature and industry. However, powered by batteries, these devices need to be recharged sooner or later to continue working. We propose a swarm-intelligence-based algorithm for automatically recharging the swarm members by calculating optimal paths while avoiding robot collisions.
Collaboration among robots to create certain patterns and move in coordination throughout a given area has been proposed and studied in different research works [1]. These emerging robot formations, once successfully built, can be used to develop collective tasks, achieved by the collaborating autonomous members of the robot group (swarm) using distributed algorithms. Well-known applications include surveillance, salvage missions, farming, representing dynamic figures, among others. Working with robot formations raises several difficult problems, such as optimal initial locations, path planning to reach the final positions, as well as avoiding collisions.
Our case study consists of a set of autonomous trolleys to be used as cargo transport platforms (Figure 1). Each trolley is able to move independently from its initial position to its desired destination avoiding collisions. To do that, they have four wheels using a 2-hinge system (yaw and traction), WiFi connectivity, and a radio frequency positioning system. The trolleys have a battery pack that needs to be periodically recharged to ensure continuous operation.
Several strategies can be used for calculating optimal paths for the trolleys, not only to build the formation, but also to transport the cargo to the desired destination. A variety of solutions ranging from greedy to bio-inspired algorithms have been proposed for trajectory planning in multi-robot systems [2]. Our approach consists of a cooperative coevolutionary genetic algorithm (CCGA) for calculating the optimal routes for each trolley. It is supported by a swarm intelligence algorithm to avoid trolley collisions, especially when the trolleys’ batteries are low, and they need to recharge at dedicated stations. Our choice is justified by the complexity of the trajectories, especially in the scenarios with several tens of moving trolleys requiring optimal, collision-free path plans.
Figure 1: Cargo trolley formation. Each trolley is equipped with four independent wheels, 2-hinge joints and WiFi connectivity.
The proposed CCGA consists of an individual genetic algorithm (GA) associated with each trolley (Figure 2). Given a trolley’s origin and destination, it calculates the optimal path while avoiding collisions with the other trolleys which are also moving towards their respective destinations. The trajectory calculation is done in advance. Once all the trajectories are known, the synchronised movement of the trolleys takes place to transport their payload. Genetic algorithms are efficient methods for solving combinatorial optimisation problems. They simulate processes present in evolution such as natural selection, gene recombination after reproduction, gene mutation, and the dominance of the fittest individuals over the weaker ones. In our proposal, each individual in the algorithm’s population corresponds to a path plan which is evaluated using a simulator to calculate its quality. High quality solutions, i.e. those which represent shorter paths that do not end up in collisions, are better valued and persist as part of the algorithm population, becoming part of the next generation. After several generations of individuals, the whole evolutionary process concludeses by converging to an optimal path for each trolley.
Figure 2: Cooperative Coevolutionary Genetic Algorithm. Each single genetic algorithm evolves its own population of individuals (path plans) corresponding to one trolley. The best solution for the transportation system is calculated by using the best individuals from each GA.
Eventually, the swarm of trolleys will exhaust their batteries, being forced to recharge. The system provides recharging stations for that purpose, placed outside of the operation area. Now, each trolley must be able to reach one station with the remaining battery charge, using the shortest path. Under these conditions, the swarm members must collaborate with each other by facilitating movement towards the recharging station. They would do it by turns, depending on the onboard remaining charge. We propose for this stage the use of potential fields as part of our swarm intelligence algorithm [3] where repelling forces act dynamically and simultaneously to place each trolley in a minimum potential location, avoiding collisions while clearing the way towards the recharging station. The use of these algorithms requires the optimisation of a set of parameters, such as force intensity, activation thresholds, minimum distances, and maximum speeds. Furthermore, each trolley communicates its position and current role to the rest of the swarm to achieve the desired, distributed intelligent behaviour.
Figure 3 shows an example of the trolleys’ trajectories in three snapshots obtained from the swarm simulator. The initial positions of the trolleys are shown in Figure 3a) where trolleys 01 and 02 have to reach their corresponding recharging station at the left of the area. As it is done sequentially, trolley 01 is the first to move forcing the others to cooperate by moving away from its trajectory as shown in Figure 3b). Next, is the turn of trolley 02, which also spreads the other trolleys when moving towards destination as it can be seen in Figure 3c). In this example, we have used our CCGA to calculate the optimal paths in combination with our proposed swarm-intelligence-based collision avoidance algorithm.
Figure 3: Example of recharging trolleys. a) the trolleys’ initial positions and the available recharging stations on the left. b) trajectories after trolley 01 has reached station 01. c) trajectories after trolley 02 has reached station 02.
The proposed cooperative robot formation system using evolutionary computation and swarm intelligence, is part of a technological demonstrator for the autonomous cargo transportation system developed in the Luxembourg Institute of Science and Technology for the CACTUS project. It relies on a swarm of trolleys which collaborate with each other to perform complex tasks, such as path planning and collision avoidance. The swarm is capable of self-recharging its onboard batteries for continuous, unmanned operation. As a future work, we plan to further develop our system and test it on actual cargo platforms to assess its viability in a real-world scenario.
References:
[1] P. G. F. Dias, et al., “Swarm Robotics: A Perspective on the Latest Reviewed Concepts and Applications,” Sensors, 2021.
[2] Á. Madridano, et al., “Trajectory planning for multi-robot systems: Methods and applications,” Expert Systems with Applications, 2021.
[3] P. Vadakkepat, et al., “Evolutionary artificial potential fields and their application in real time robot path planning,” in Proceedings of the 2000 Congress on Evolutionary Computation. CEC00, 2000.
Please contact:
Daniel H. Stolfi, Luxembourg Institute of Science and Technology, Luxembourg
