´óÏó´«Ã½

When managing large agricultural fields, monitoring extensive forests for fire prevention, or exploring natural resource sites, it is crucial to have efficient, timely and reliable information. One way to meet the challenges of surveying vast areas is to deploy teams of robots.

Coverage path planning (CPP) is a fundamental robotics problem that involves designing paths for robots to systematically cover every part of an environment—similar to how farmers harvest crops by moving through rows. Traditional methods using single robots can be slow and lack coverage capabilities, while teams of coordinated robots can accomplish tasks much more effectively.

At ´óÏó´«Ã½ (´óÏó´«Ã½), computing science professor researches and teaches robotics, robot systems, artificial intelligence (AI) and machine learning. His innovative work significantly advances robotic coordination and demonstrates the substantial benefits of multi-robot systems over traditional single-robot approaches.

By improving efficiency and robustness, Ma’s research is shaping the future of robotic systems and contributing to better outcomes in agriculture, environmental management and resource exploration which are crucial to Canada’s economy and sustainability.

His paper, , with computing science PhD student Jingtao Tang, was one of the top-cited academic papers from ´óÏó´«Ã½ in 2024. The research looks at multi-robot coverage path planning (MCPP), to coordinate the paths of robots to completely cover an area. The new research improves upon existing algorithms, enabling MCPP to consider a two-dimensional field and cover all vertices like a forest of multiple trees.

The new model developed by Ma significantly reduces makespan—the total time required to complete the task. Multiple robots and improved efficiency means MCPP can facilitate important real-world tasks from search and rescue to resource management to forest fire prevention.

We spoke with Professor Ma about his research.

Can you explain how your approach improves upon existing search algorithms?

Existing algorithms for multi-robot coverage path planning (MCPP) typically rely on decomposing the coverage area into tree-like structures and then generating paths by navigating around those trees. However, this method can lead to inefficiencies and uneven workloads among robots.

Our research takes a more direct and systematic approach, introducing a novel algorithmic framework called LS-MCPP. LS-MCPP leverages a ‘local search’ strategy combined with a new paradigm we developed called Extended Spanning Tree Coverage (ESTC). Unlike traditional methods, our approach directly optimizes the paths by actively exploring various coverage configurations to significantly reduce the task completion time, or makespan.

How did you test your new algorithmic framework, and how did it compare to standard methods?

We conducted extensive experiments to evaluate LS-MCPP against established baseline algorithms. The results consistently demonstrated that our method significantly improved efficiency, reducing makespan by as much as 35.7 percent compared to state-of-the-art methods.

Moreover, our algorithm achieved these superior results which dramatically reduced computation times—from hours required by conventional methods to mere minutes. This highlights the practicality and efficiency of LS-MCPP for large-scale operational tasks, which we , while presenting real robot experiments.

What are some of the applications for this algorithm—where one would use multiple robots to cover an area?

Our algorithm is particularly beneficial in agriculture, natural resource management, and environmental protection—areas highly relevant to Canada. For example, teams of robots equipped with our planning method could efficiently perform automated planting and crop harvesting over vast agricultural lands, greatly enhancing productivity and reducing human labor costs.

In forestry management, robots guided by our system can patrol remote forest regions, providing early detection of potential fire hazards and significantly improving wildfire prevention efforts. Multi-robot solutions offer considerable advantages over single-robot systems by completing tasks much faster, covering larger areas simultaneously, and providing built-in redundancy—if one robot fails, others can seamlessly take over its coverage responsibilities.

Is the algorithm something that would be patented, or would it be shared with other computing scientists?

Our goal is to make this framework widely accessible to researchers and industry practitioners. We believe that open sharing promotes collaboration and accelerates innovation in robotics and AI. The code for our LS-MCPP algorithm is openly available online at: , allowing others to apply, adapt and extend our work across diverse applications, benefiting both academia and industry broadly.

For more: see the extended journal version of the research paper (accepted for publication at IEEE Transactions on Robotics), preprint available at: