Algorithms for Mobile Robots
Recently, efforts have been made to improve the efficiency of delivery and other operations in production plants by using multiple autonomous mobile robots to work cooperatively. As production plants become larger and the number of robots increases, it becomes difficult to control each robot centrally. Therefore, we are developing algorithms to achieve various tasks under the conditions that each robot needs to observe information in a limited area and make decisions and move autonomously based on that information. We are also experimenting with 150 kilobots and 15 Khepra IVs to demonstrate the algorithms we have developed.
Fig.1: kilobot
Fig.2: Khepra IV
Exploration and Gathering in Rings
We modeled the environment in which the robot operates with ring graph where each robot can only see the robots that exist within a distance Φ from it, and developed algorithms to explore the entire environment and to gather all the robots at one place. In order to reduce the cost of robots, these tasks need to be accomplished with the least functional robot possible. In the following works, we model the communication and memory capabilities of the robot with a function of light, and show its optimality.
Fault Tolerance for Byzantine Failures
When many robots are cooperating, there is a possibility that some of them may behave abnormally due to software bugs or viruses. In this research, we modeled such failures as Byzantine failures and developed algorithms to deal with Byzantine failures. Specifically, we find the Byzantine failure and surround it with other robots so that the Byzantine failure does not adversely affect the whole system. We also propose a Forgive-and-forget approach, which we won't go into detail about, but we periodically forget about robots with Byzantine failures in order to achieve self-stabilization. (In collaboration with Negev-Bengurion University, Israel)