Researchers have developed geometric algorithms that can make groups of robots operate together in dense environments without bumping into each other and other obstacles
Robots should be able to move independently, sense and change the environment, without colliding with the objects around them. The more robots there are, the more complex these tasks become. The robots are required to avoid colliding with each other, even when they are required to perform an activity together, when they are very close to each other, for example, to lift a heavy object. Today, the use of groups of robots is becoming more common and necessary, and therefore methods are required to make them work together in coordination and efficiency.
Robotics is based on a variety of fields, one of which is computational geometry - a field in computer science that deals with the development of algorithms for solving geometric problems. With the exception of robotics, it is applied in many other fields, including computer vision, geographic information systems and civil engineering (for example, it is possible to plan an efficient network of buildings and areas with cameras, transmitters and antennas.
"Computational geometry developed alongside research in robotics and these fields greatly influence each other. For example, using geometric algorithms it is possible to map areas, divide them into zones, place objects at strategic points and make movement decisions. And if you want, for example, a robot to move along the shortest path, achieve the goal and stay away from obstacles, you build a geometric algorithm that translates into commands that help it do this," explains Prof. Dan Halperin from the School of Computer Science at Tel Aviv University.
Prof. Halperin deals with computational geometry, develops geometric algorithms and was a partner in a European project to produce software for their implementation (The Computational Geometry Algorithms Library - CGAL). In one of his latest studies, which won a research grant from the National Research Foundation, and which was presented at a major robotics conference (ICRA 2021) in China, he developed algorithms for groups of robots together with his team and in collaboration with researchers from Stanford University. According to him, "We know how to design algorithms for a single robot, which make it move efficiently, but it is more difficult to build algorithms that will make several robots move together properly, be coordinated and cooperate. The more robots there are and the denser the work environment (when the robots are very close to each other and to obstacles) - the computational difficulty is greater. But it is essential, as the use of a fleet of robots, in commercial and civilian applications, is increasing. For example, it is applied in huge warehouses such as those of Amazon, various industrial plants, disaster areas, and 'flocks' of drones that visit large buildings and bridges and protect nature reserves. Using a fleet of robots, you can achieve goals much faster, be efficient and economical."
The geometric algorithms developed by Prof. Halperin and research student Dror Dayan, in collaboration with Prof. Makro Pavona from Stanford University and Prof. Kirill Solovyi from the Technion, are sampling-based (they sample possible movement states of the robots and decide if they are legal. That is, if they prevent the robots from colliding with obstacles and each other ), and plan joint movement of groups of robots. Their uniqueness is that they guarantee the quality of the robots' routes using a number of movement samples known in advance.
"We know exactly how many samples are needed to get a certain level of optimality," explains Prof. Halperin. With the help of the algorithms, the researchers build a road map that approximates all the legal configurations on the route. Such a map is drawn for each robot separately and then all the maps, of all the robots, are sewn together. The sewing makes it possible to move all the robots together, at the same time, without them encountering obstacles and each other. The method works in every dimension, and thus is also effective for robots with many degrees of freedom of movement.
The researchers implemented the algorithms in software that simulates the operation of several robots at the same time and discovered that even in crowded situations they lead to near-optimal solutions. For example, they were able to move from point to point in a very small room (relative to the size and number of robots) or change places without colliding with each other and other obstacles. According to Prof. Halperin, "in comparative experiments with the latest methods in robotics, we saw that the new method is the only one that approaches optimal solutions in crowded environments. It is true that more studies are needed to evaluate it, but already now it can be seen that its starting point is better than that of the existing methods."
Life itself:
Prof. Dan Halperin lives with his partner and 19-year-old daughter in Tel Aviv. In his spare time he likes to play and listen to music.
