Japanese

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.

Fig1: kilobot

Fig.1: kilobot

Fig2: Khepra IV

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.

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sebastien Tixeuil, and Koichi Wada, "Gathering on rings for myopic asynchronous robots with lights", Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS), Dec. 2019.

Shota Nagahama, Fukuhito Ooshita, and Michiko Inoue, "Ring exploration of myopic luminous robots with visibility more than one", Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Oct. 2019. (Best Student Paper Award)

Fukuhito Ooshita and Sebastien Tixeuil, "Ring exploration with myopic luminous robots", Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 301-316, Nov. 2018.

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)

Yotam Ashkenazi, Shlomi Dolev, Sayaka Kamei, Fukuhito Ooshita, and Koichi Wada, "Brief announcement: Forgive & Forget: Self-Stabilizing Swarms in Spite of Byzantine Robots", Proceedings of the 21st International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Oct. 2019 (Brief Announcement).