Recently, you may have seen thousands of drones flying in the sky, making a spectacular aerial show on a special occasion. This “Drone Show”, like an artwork, is a combination of highly advanced technology, artistic touch, and various other factors in action. What roles then will drones play in the future, other than this kind of clustered flight? Robots, including drones, will play various and rather complicated roles in line with the advancement of related technologies. Accordingly, scientists searching for more efficient ways to operate multi-robot systems should play bigger roles too. Professor Choi, Han-Lim and his team have studied how to make multiple robots (“Multi-robots”) satisfy regulations, constraints, and rules while carrying out complicated missions. They have recently succeeded in developing an algorithm that can more effectively handle missions, routes, and planning of multi-robots.

New algorithms to handle complicated missions

Prof. Choi and his team have developed an algorithm that can effectively handle missions, routes, and planning of multirobot operations. This algorithm helps define a route for each drone when a large number of drones are active in a vast area for forest fire monitoring or crop management, for example. If the location subject to monitoring or observation is a dense space, the mobility constraints of the robots should be taken into consideration, or missions in such places would be impossible to carry out. As such, mobility constraints must be considered for observation missions of multiple observation locations using UAVs or ground excursion robots with limited turn radius (TR).

What Prof. Choi’s team has developed is an algorithm for designing efficient routes and task sequences simultaneously for multiple observatory robots with mobility constraints on multiple missions in largely dispersed locations. The team has developed an optimization technique to effectively calculate
the Generalized, Heterogeneous, Multiple depot, Asymmetric Traveling Salesmen Problem (GHMDATSP) for tour design of multiple observatory robots. When approaching GHMDATSP based on sampling, candidate sites for a mission are sampled for each mission point, so it may be necessary for a single robot to visit two very close observation points. To reduce such redundancy, Prof. Choi and his team introduced the concept of NIN (Necessarily-Intersecting-Neighborhood), and further extended it, considering a sensing model called NIR (Necessarily-Intersection-Region). The team has confirmed,
based on tour calculation, that the workload among the robots was properly distributed when multiple robots performed observation tasks using the proposed algorithm.


The algorithm will help efficient operation of the multi-robot system in various platforms

Prof. Choi said, “Nowadays, robots are playing wide-ranging roles, from smart agriculture, environment, to even disaster controls. And there are many factors to consider when operating multiple robots at once.” The team expects that the algorithm will help operate multi-robot systems more efficiently in diverse various platforms, including drone cars. The algorithm and the team’s achievement were published in International Journal of Systems Science in March 2020.


Prof. Choi, Han-Lim
2020 KI Annual Report