IDEAS home Printed from https://ideas.repec.org/a/gam/jeners/v15y2022i21p7898-d952210.html
   My bibliography  Save this article

A Divide and Conquer Strategy for Sweeping Coverage Path Planning

Author

Listed:
  • Juan Irving Vasquez

    (Instituto Politécnico Nacional, Centro de Innovación y Desarrollo Tecnológico en Cómputo, Ciudad de México 07700, Mexico
    These authors contributed equally to this work.)

  • Emmanuel Alejandro Merchán-Cruz

    (SIA Robotic Solutions, LV-1039 Riga, Latvia
    Transport and Telecommunication Institute, LV-1019 Riga, Latvia
    These authors contributed equally to this work.)

Abstract

One of the main challenges faced by floor treatment service robots is to compute optimal paths that completely cover a set of target areas. Short paths are of noticeable importance because their length is directly proportional to the energy used by the robot. Such a problem is known to be NP-hard; therefore, efficient algorithms are needed. In particular, computation efficiency is important for mobile robots with limited onboard computation capability. The general problem is known as coverage path planning (CPP). The CPP has several variants for single regions and for disjoint regions. In this research, we are investigating the solutions for disjoint target regions (rooms) that have fixed connection points (doors). In particular, we have found effective simplifications for the cases of rooms with one and two doors, while the challenging case of an unbounded number of rooms can be solved by approximation. As a result, this work presents a divide and conquer strategy (DnCS) to address the problem of finding a path for a sweeping robot that needs to sweep a set of disjoint rooms that are connected by fixed doors and corridors. The strategy divides the problem into computing the sweeping paths for the target rooms and then merges those paths into one solution by optimising the room visiting order. In this strategy, a geometrical approach for room coverage and an undirected rural postman problem optimisation are strategically combined to solve the coverage of the entire area of interest. The strategy has been tested in several synthetic maps and a real scenario showing short computation times and complete coverage.

Suggested Citation

  • Juan Irving Vasquez & Emmanuel Alejandro Merchán-Cruz, 2022. "A Divide and Conquer Strategy for Sweeping Coverage Path Planning," Energies, MDPI, vol. 15(21), pages 1-15, October.
  • Handle: RePEc:gam:jeners:v:15:y:2022:i:21:p:7898-:d:952210
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1996-1073/15/21/7898/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/1996-1073/15/21/7898/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Jianbin Xin & Benyang Yu & Andrea D’Ariano & Heshan Wang & Meng Wang, 2022. "Time-dependent rural postman problem: time-space network formulation and genetic algorithm," Operational Research, Springer, vol. 22(3), pages 2943-2972, July.
    2. Anh Vu Le & Ping-Cheng Ku & Thein Than Tun & Nguyen Huu Khanh Nhan & Yuyao Shi & Rajesh Elara Mohan, 2019. "Realization Energy Optimization of Complete Path Planning in Differential Drive Based Self-Reconfigurable Floor Cleaning Robot," Energies, MDPI, vol. 12(6), pages 1-23, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Manivannan Kalimuthu & Thejus Pathmakumar & Abdullah Aamir Hayat & Prabakaran Veerajagadheswar & Mohan Rajesh Elara & Kristin Lee Wood, 2023. "Optimal Morphologies of n-Omino-Based Reconfigurable Robot for Area Coverage Task Using Metaheuristic Optimization," Mathematics, MDPI, vol. 11(4), pages 1-23, February.
    2. Adamo, Tommaso & Gendreau, Michel & Ghiani, Gianpaolo & Guerriero, Emanuela, 2024. "A review of recent advances in time-dependent vehicle routing," European Journal of Operational Research, Elsevier, vol. 319(1), pages 1-15.
    3. Arunmozhi Manimuthu & Anh Vu Le & Rajesh Elara Mohan & Prabahar Veerajagadeshwar & Nguyen Huu Khanh Nhan & Ku Ping Cheng, 2019. "Energy Consumption Estimation Model for Complete Coverage of a Tetromino Inspired Reconfigurable Surface Tiling Robot," Energies, MDPI, vol. 12(12), pages 1-18, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jeners:v:15:y:2022:i:21:p:7898-:d:952210. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.