robot task assignment algorithm

A Sequential Task Addition Distributed Assignment Algorithm for Multi-Robot Systems

• Regular paper
• Published: 31 May 2021
• Volume 102 , article number  51 , ( 2021 )

Cite this article

• Nathan Lindsay   ORCID: orcid.org/0000-0001-6448-7012 1 ,
• Russell K. Buehling 1 &
• Liang Sun 1  

400 Accesses

8 Citations

5 Altmetric

Explore all metrics

In this paper, we present a novel distributed task-allocation algorithm, namely the Sequential Task Addition Distributed Assignment Algorithm (STADAA), for autonomous multi-robot systems. The proposed STADAA can implemented in applications such as search and rescue, mobile-target tracking, and Intelligence, Surveillance, and Reconnaissance (ISR) missions. The proposed STADAA is developed by modifying an algorithm (i.e., the Task Oriented Distributed Assignment Algorithm (TODAA)) we previously developed based on the Hungarian algorithm. The STADAA employs a conflict-resolution mechanism that utilizes a slack variable, sequentially adding new admissible tasks to an admissible task list when there exists conflict in an assignment. The STADAA aims to minimize the resulting cost of the task assignments. We compare the STADAA with the Consensus-Based Auction Algorithm (CBAA), the Distributed Hungarian Based Algorithm (DHBA), and the TODAA in terms of the computational time, optimality, the number of steps to converge, and algorithmic complexity. The results show that the STADAA outperforms the CBAA and the TODAA in optimality and outperforms the DHBA in computational time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Dynamic multi-robot task allocation under uncertainty and temporal constraints

Auction-Based Task Allocation and Motion Planning for Multi-Robot Systems with Human Supervision

Cooperative Multi-agent Systems for the Multi-target $$\upkappa $$ -Coverage Problem

Explore related subjects.

• Artificial Intelligence

Data Availability

The supporting data of the information presented in this manuscript is available from the corresponding author, Nathan Lindsay, upon reasonable request.

Abdallah, S., Lesser, V.: Learning the task allocation game. In: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pp. 850–857 (2006)

Bellingham, J., Tillerson, M., Richards, A., How, J. P.: Multi-task allocation and path planning for cooperating uavs. In: Cooperative control: models, applications and algorithms, pp. 23–41. Springer (2003)

Bertsekas, D.P.: Auction algorithms for network flow problems: A tutorial introduction. Comput. Optim. Appl. 1 (1), 7–66 (1992)

Article   MathSciNet   Google Scholar  

Binetti, G., Davoudi, A., Naso, D., Turchiano, B., Lewis, F.L.: A distributed auction-based algorithm for the nonconvex economic dispatch problem. IEEE Trans. Ind. Inf. 10 (2), 1124–1132 (2013)

Article   Google Scholar  

Burkard, R. E., Derigs, U.: Assignment and matching problems: solution methods with FORTRAN-programs, vol. 184. Springer Science & Business Media, Berlin (2013)

Google Scholar  

Choi, H. L., Brunet, L., How, J. P.: Consensus-based decentralized auctions for robust task allocation. IEEE Trans. Robot. 25 (4), 912–926 (2009)

Chopra, S., Notarstefano, G., Rice, M., Egerstedt, M.: A distributed version of the hungarian method for multirobot assignment. IEEE Trans. Robot. 33 (4), 932–947 (2017)

Choudhury, S., Gupta, J. K., Kochenderfer, M. J., Sadigh, D., Bohg, J.: Dynamic multi-robot task allocation under uncertainty and temporal constraints. arXiv: 2005.13109 (2020)

Dames, P. M.: Distributed multi-target search and tracking using the phd filter. Auton. Robot., 1–17 (2019)

Farmani, N., Sun, L., Pack, D. J.: A scalable multitarget tracking system for cooperative unmanned aerial vehicles. IEEE Trans. Aerosp. Electron. Syst. 53 (4), 1947–1961 (2017)

Hu, J., Yang, J.: Application of distributed auction to multi-uav task assignment in agriculture. Int. J. Precision Agricultural Aviation 1 (1) (2018)

Ismail, S., Sun, L.: Decentralized hungarian-based approach for fast and scalable task allocation. In: 2017 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 23–28. IEEE (2017)

Johnson, L., Ponda, S., Choi, H. L., How, J.: Asynchronous decentralized task allocation for dynamic environments. In: Infotech@ Aerospace 2011, p. 1441 (2011)

Kuhn, H. W.: The hungarian method for the assignment problem. Naval Res. Logist. Q. 2 (1-2), 83–97 (1955)

Lerman, K., Jones, C., Galstyan, A., Matarić, M. J.: Analysis of dynamic task allocation in multi-robot systems. Int. J. Robot. Res. 25 (3), 225–241 (2006)

Lin, C.: Online connectivity-aware dynamic distribution for heterogeneous multi-robot systems. Ph.D. thesis, Carnegie Mellon University Pittsburgh, PA (2020)

Lindsay, N., Sun, L.: A task-oriented distributed assignment algorithm for collaborative unmanned aerial systems. In: Proc. of 2020 IEEE International Conference on Unmanned Aircraft Systems, Athens, Greece, September 2020, accepted (2020)

Makkapati, V. R., Tsiotras, P.: Apollonius allocation algorithm for heterogeneous pursuers to capture multiple evaders. arXiv: 2006.10253 (2020)

Mills-Tettey, G.A., Stentz, A., Dias, M.B.: The dynamic hungarian algorithm for the assignment problem with changing costs. Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-07-27 (2007)

Muhuri, P.K., Rauniyar, A.: Immigrants based adaptive genetic algorithms for task allocation in multi-robot systems. Int. J. Comput. Intell. Appl. 16 (04), 1750025 (2017)

Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5 (1), 32–38 (1957)

Naparstek, O., Leshem, A.: Fully distributed auction algorithm for spectrum sharing in unlicensed bands. In: 2011 4th IEEE International Workshop On Computational Advances In Multi-Sensor Adaptive Processing (CAMSAP), pp. 233–236. IEEE (2011)

Narayanan, A., Nagarathnam, B.B., Meyyappan, M., Mongkolsri, S.: Experimental comparison of hungarian and auction algorithms to solve the assignment problem. https://chalamy.tripod.com/Report.pdf . Accessed 04 October 2020 (2000)

Omara, F. A., Arafa, M. M.: Genetic algorithms for task scheduling problem. In: Foundations of Computational Intelligence Volume 3, pp. 479–507. Springer (2009)

Pang, Y., Liu, R.: Trust aware emergency response for a resilient human-swarm cooperative system. arXiv: 2006.15466 (2020)

Papadimitriou, C. H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Courier Corporation, Chelmsford (1998)

MATH   Google Scholar  

Samiei, A., Ismail, S., Sun, L.: Cluster-based hungarian approach to task allocation for unmanned aerial vehicles. In: 2019 IEEE National Aerospace and Electronics Conference (NAECON), pp. 148–154. IEEE (2019)

Samiei, A., Sun, L.: Distributed recursive hungarian-based approaches to fast task allocation for unmanned aircraft systems. In: AIAA Scitech 2020 Forum, pp. 0658 (2020)

Schwartz, R., Tokekar, P.: Robust multi-agent task assignment in failure-prone and adversarial environments. arXiv: 2007.00100 (2020)

Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 101 (1-2), 165–200 (1998)

Sokol, V.: On some nonlinear assignment problems. Ph.D. thesis, Applied Sciences, School of Computing Science (2018)

Song, T., Yan, X., Liang, A., Chen, K., Guan, H.: A distributed bidirectional auction algorithm for multirobot coordination. In: 2009 International Conference on Research Challenges in Computer Science, pp. 145–148. IEEE (2009)

Sun, X., Qi, N., Yao, W.: Boolean networks-based auction algorithm for task assignment of multiple uavs. Math. Probl. Eng. 2015 (2015)

Suslova, E., Fazli, P.: Decentralized multi-robot task allocation with time window and ordering constraints. https://pooyanfazli.com/publications/Suslova_RSS2020W.pdf . Accessed 08 January 2021 (2017)

Zahedi, Z., Sengupta, S., Kambhampati, S.: Why not give this work to them?’explaining ai-moderated task-allocation outcomes using negotiation trees. arXiv: 2002.01640 (2020)

Zavlanos, M. M., Spesivtsev, L., Pappas, G. J.: A distributed auction algorithm for the assignment problem. In: 2008 47th IEEE Conference on Decision and Control, pp. 1212–1217. IEEE (2008)

Download references

This work was supported by the New Mexico Space Grant Consortium and the Laboratory Directed Research and Development program at Sandia National Laboratories. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology Engineering Solutions of Sandia, LLC, a wholly-owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525. The views expressed in the article do not necessarily represent the views of the U.S. Department of Energy or the United States Government.

Author information

Authors and affiliations.

New Mexico State University, Las Cruces, NM, USA

Nathan Lindsay, Russell K. Buehling & Liang Sun

You can also search for this author in PubMed   Google Scholar

Contributions

The first author, Nathan Lindsay, developed the algorithm proposed (Sequential Task Addition Distributed Assignment Algorithm - STADAA) in this paper and developed the code for the STADAA, the Consensus Based Auction Algorithm, and the Task Oriented Distributed Assignment Algorithm, which were all used in testing. Also, he wrote the first draft of this manuscript, analyzing the test results and providing insight into the algorithm’s performance. The second author, Russell Buehling, developed the code for the Distributed Hungarian Based Algorithm that was used in testing, developed the testing environment and ran the tests that generated the results displayed in this paper. The third author, Liang Sun, as the research advisor of the first and second authors, initiated the research work presented in the paper, developed the research plan for methodologies, simulations, experiments, analysis, and data collection, provided guidance for research discussions. All authors read and approved the revised manuscript.

Corresponding author

Correspondence to Nathan Lindsay .

Ethics declarations

Ethics approval.

We deemed no ethical approval was necessary.

Consent for Publication

All authors confirm that: - The research done in this paper has not been published before. - This is not considered for publication anywhere else. - All coauthors approve the publication of this information.

All authors willfully consent to having their information being published in the Journal of Intelligent and Robotic Systems. We understand that the test results and images published in this article will be published on an open access basis and will be freely available on the internet and may be seen by the general public. We reserve the right to revoke our consent for publication at any time prior to publication, but we acknowledge that once the information has been committed to publication, revocation of our consent is no longer possible.

Competing interests

All authors affirm that there is no known conflict of interest pertaining to the information presented in this manuscript.

Additional information

Consent to participate.

All mentioned authors voluntarily agreed to participate in this research topic.

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Previous paper “A Task-Oriented Distributed Assignment Algorithm for Collaborative Unmanned Aerial Systems” in proceedings of the 2020 International Conference on Unmanned Aircraft Systems (ICUAS’20), Athens, Greece

Rights and permissions

Reprints and permissions

About this article

Lindsay, N., Buehling, R.K. & Sun, L. A Sequential Task Addition Distributed Assignment Algorithm for Multi-Robot Systems. J Intell Robot Syst 102 , 51 (2021). https://doi.org/10.1007/s10846-021-01394-2

Download citation

Received : 06 October 2020

Accepted : 08 April 2021

Published : 31 May 2021

DOI : https://doi.org/10.1007/s10846-021-01394-2

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Task assignment
• Autonomous systems
• Optimization
• Multi-robot systems
• Distributed systems

Advertisement

• Find a journal
• Publish with us
• Track your research

An official website of the United States government

The .gov means it’s official. Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

The site is secure. The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

• Publications
• Account settings
• My Bibliography
• Collections
• Citation manager

Save citation to file

Email citation, add to collections.

• Create a new collection
• Add to an existing collection

Add to My Bibliography

Your saved search, create a file for external citation management software, your rss feed.

• Search in PubMed
• Search in NLM Catalog
• Add to Search

Multi-robot task assignment for serving people quarantined in multiple hotels during COVID-19 pandemic

Affiliations.

• 1 Shenzhen University, College of Mechatronics and Control Engineering, Shenzhen, China.
• 2 Shenzhen City Joint Laboratory of Autonomous Unmanned Systems and Intelligent Manipulation, Shenzhen University, Shenzhen, China.
• 3 Shenzhen University, College of Physics and Optoelectronic Engineering, Shenzhen, China.
• 4 Shenzhen Institute of Artificial Intelligence and Robotics for Society (AIRS), Shenzhen, China.
• PMID: 36915326
• PMCID: PMC10006103
• DOI: 10.21037/qims-22-842

Background: Efficiently combating with the coronavirus disease 2019 (COVID-19) has been challenging for medics, police and other service providers. To reduce human interaction, multi-robot systems are promising for performing various missions such as disinfection, monitoring, temperature measurement and delivering goods to people quarantined in prescribed homes and hotels. This paper studies the task assignment problem for multiple dispersed homogeneous robots to visit a set of prescribed hotels to perform tasks such as body temperature assessment or oropharyngeal swabs for people quarantined in the hotels while trying to minimize the robots' total operation time. Each robot can move to multiple hotels sequentially within its limited maximum operation time to provide the service.

Methods: The task assignment problem generalizes the multiple traveling salesman problem, which is an NP-hard problem. The main contributions of the paper are twofold: (I) a lower bound on the robots' total operation time to serve all the people has been found based on graph theory, which can be used to approximately evaluate the optimality of an assignment solution; (II) several efficient marginal-cost-based task assignment algorithms are designed to assign the hotel-serving tasks to the robots.

Results: In the Monte Carlo simulations where different numbers of robots need to serve the people quarantined in 30 and 90 hotels, the designed task assignment algorithms can quickly (around 30 ms) calculate near-optimal assignment solutions (within 1.15 times of the optimal value).

Conclusions: Numerical simulations show that the algorithms can lead to solutions that are close to the optimal compared with the competitive genetic algorithm and greedy algorithm.

Keywords: Multi-robot systems; coronavirus disease 2019 (COVID-19); lower bound; marginal cost; task assignment.

2023 Quantitative Imaging in Medicine and Surgery. All rights reserved.

PubMed Disclaimer

Conflict of interest statement

Conflicts of Interest: All authors have completed the ICMJE uniform disclosure form (available at https://qims.amegroups.com/article/view/10.21037/qims-22-842/coif). The authors have no conflicts of interest to declare.

The robot offered by Cityeasy…

The robot offered by Cityeasy Technology can move around schools, hotels and airports…

The flowchart of TSTMCA. TSTMCA,…

The flowchart of TSTMCA. TSTMCA, total serving time based marginal cost algorithm.

The flowchart of TTMCA(d). TTMCA,…

The flowchart of TTMCA(d). TTMCA, travel time based marginal cost algorithm; TTMCA(d), algorithm…

The flowchart of TTMCA(c). TTMCA,…

The flowchart of TTMCA(c). TTMCA, travel time based marginal cost algorithm; TTMCA(c), algorithm…

The robots’ average total operation…

The robots’ average total operation time (s) serve all the people quarantined in…

The average solution quality ratios…

The average solution quality ratios of the algorithms for different numbers of robots…

The robots’ average total operation time (s) to serve all the people quarantined…

The average solution quality ratios r of the algorithms for different numbers of…

The robots’ routes to serve…

The robots’ routes to serve the 21 target locations guided by TTMCA(c), where…

The robots’ routes to serve the 21 target locations guided by GA, where…

The robots’ routes to serve the 21 target locations guided by CMGA, where…

The routes for 3 robots…

The routes for 3 robots to serve 21 target locations guided respectively by…

Similar articles

• Research on a hybrid neural network task assignment algorithm for solving multi-constraint heterogeneous autonomous underwater robot swarms. Ru J, Hao D, Zhang X, Xu H, Jia Z. Ru J, et al. Front Neurorobot. 2023 Jan 10;16:1055056. doi: 10.3389/fnbot.2022.1055056. eCollection 2022. Front Neurorobot. 2023. PMID: 36704716 Free PMC article.
• A Convex Optimization Approach to Multi-Robot Task Allocation and Path Planning. Lei T, Chintam P, Luo C, Liu L, Jan GE. Lei T, et al. Sensors (Basel). 2023 May 26;23(11):5103. doi: 10.3390/s23115103. Sensors (Basel). 2023. PMID: 37299829 Free PMC article.
• Blockchain-Empowered Multi-Robot Collaboration to Fight COVID-19 and Future Pandemics. Alsamhi SH, Lee B. Alsamhi SH, et al. IEEE Access. 2020 Oct 26;9:44173-44197. doi: 10.1109/ACCESS.2020.3032450. eCollection 2021. IEEE Access. 2020. PMID: 34786312 Free PMC article.
• Learning-based control approaches for service robots on cloth manipulation and dressing assistance: a comprehensive review. Nocentini O, Kim J, Bashir ZM, Cavallo F. Nocentini O, et al. J Neuroeng Rehabil. 2022 Nov 3;19(1):117. doi: 10.1186/s12984-022-01078-4. J Neuroeng Rehabil. 2022. PMID: 36329473 Free PMC article. Review.
• Recent Advances in Bipedal Walking Robots: Review of Gait, Drive, Sensors and Control Systems. Mikolajczyk T, Mikołajewska E, Al-Shuka HFN, Malinowski T, Kłodowski A, Pimenov DY, Paczkowski T, Hu F, Giasin K, Mikołajewski D, Macko M. Mikolajczyk T, et al. Sensors (Basel). 2022 Jun 12;22(12):4440. doi: 10.3390/s22124440. Sensors (Basel). 2022. PMID: 35746222 Free PMC article. Review.
• Particle Swarm Algorithm Path-Planning Method for Mobile Robots Based on Artificial Potential Fields. Zheng L, Yu W, Li G, Qin G, Luo Y. Zheng L, et al. Sensors (Basel). 2023 Jul 1;23(13):6082. doi: 10.3390/s23136082. Sensors (Basel). 2023. PMID: 37447930 Free PMC article.
• Fauci AS, Lane HC, Redfield RR. Covid-19 - Navigating the Uncharted. N Engl J Med 2020;382:1268-9. 10.1056/NEJMe2002387 - DOI - PMC - PubMed
• Agarwal S, Punn NS, Sonbhadra SK, Tanveer M, Nagabhushan P, Pandian K, Saxena P. Unleashing the power of disruptive and emerging technologies amid COVID-19: A detailed review. arXiv preprint arXiv:2005.11507 2020:1-60.
• Bogue R. Robots in a contagious world. Industrial Robot 2020;47:637-42. 10.1108/IR-05-2020-0101 - DOI
• Available online: http://www.manbu.cc/index.php?id=2489 (accessed on 16 November 2022).
• Yang GZ, J Nelson B, Murphy RR, Choset H, Christensen H, H Collins S, Dario P, Goldberg K, Ikuta K, Jacobstein N, Kragic D, Taylor RH, McNutt M. Combating COVID-19-The role of robotics in managing public health and infectious diseases. Sci Robot 2020;5:eabb5589. 10.1126/scirobotics.abb5589 - DOI - PubMed

LinkOut - more resources

Full text sources.

• AME Publishing Company
• Europe PubMed Central
• PubMed Central

Miscellaneous

• NCI CPTAC Assay Portal

• Citation Manager

NCBI Literature Resources

MeSH PMC Bookshelf Disclaimer

The PubMed wordmark and PubMed logo are registered trademarks of the U.S. Department of Health and Human Services (HHS). Unauthorized use of these marks is strictly prohibited.

Information

• Author Services

Initiatives

You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .

Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.

Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.

Original Submission Date Received: .

• Active Journals
• Find a Journal
• Proceedings Series
• For Authors
• For Reviewers
• For Editors
• For Librarians
• For Publishers
• For Societies
• For Conference Organizers
• Open Access Policy
• Institutional Open Access Program
• Special Issues Guidelines
• Editorial Process
• Research and Publication Ethics
• Article Processing Charges
• Testimonials
• Preprints.org
• SciProfiles
• Encyclopedia

Article Menu

• Subscribe SciFeed
• Recommended Articles
• Google Scholar
• on Google Scholar
• Table of Contents

Find support for a specific problem in the support section of our website.

Please let us know what you think of our products and services.

Visit our dedicated information section to learn more about MDPI.

JSmol Viewer

Multi-robot collaborative mapping with integrated point-line features for visual slam.

1. Introduction

2. related work, 3. visual mileage calculation method based on point and line features, 3.1. feature extraction and matching of point and line features.

3.2. Error Model and Pose Estimation Based on Point-Line Features

3.3. building local maps, 4. map-fusion algorithm based on scene recognition, 4.1. keyframe selection, 4.2. visual bag of words method for determining areas of overlap, 4.3. relative pose computation, 4.4. map fusion.

5. Experiments

5.1. details, 5.2. performance, 5.2.1. experimental testing of enhanced point-line feature-extraction algorithm, 5.2.2. map-fusion experiment, 6. conclusions, author contributions, institutional review board statement, informed consent statement, data availability statement, conflicts of interest.

• Xia, Y.; Zhu, J.; Zhu, L. Dynamic role discovery and assignment in multi-agent task decomposition. Complex Intell. Syst. 2023 , 9 , 6211–6222. [ Google Scholar ] [ CrossRef ]
• Gautam, A.; Mohan, S. A review of research in multi-robot systems. In Proceedings of the 2012 IEEE 7th international conference on industrial and information systems (ICIIS), Madras, India, 6–9 August 2012; IEEE: Piscataway, NJ, USA, 2012; pp. 1–5. [ Google Scholar ]
• Wu, C.; Agarwal, S.; Curless, B.; Seitz, S.M. Multicore bundle adjustment. In Proceedings of the CVPR 2011, Colorado Springs, CO, USA, 20–25 June 2011; IEEE: Piscataway, NJ, USA, 2011; pp. 3057–3064. [ Google Scholar ]
• Rosten, E.; Drummond, T. Machine learning for high-speed corner detection. In Computer Vision–ECCV 2006: Proceedings of the 9th European Conference on Computer Vision, Graz, Austria, May 7–13, 2006, Proceedings, Part I 9 ; Springer: Berlin/Heidelberg, Germany, 2006; pp. 430–443. [ Google Scholar ]
• Calonder, M.; Lepetit, V.; Strecha, C.; Fua, P. Brief: Binary robust independent elementary features. In Computer Vision–ECCV 2010: Proceedings of the 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5–11, 2010, Proceedings, Part IV 11 ; Springer: Berlin/Heidelberg, Germany, 2010; pp. 778–792. [ Google Scholar ]
• Engel, J.; Sturm, J.; Cremers, D. Semi-dense visual odometry for a monocular camera. In Proceedings of the IEEE International Conference on Computer Vision, Sydney, Australia, 1–8 December 2013; pp. 1449–1456. [ Google Scholar ]
• Engel, J.; Schöps, T.; Cremers, D. LSD-SLAM: Large-scale direct monocular SLAM. In Proceedings of the European Conference on Computer Vision, Zurich, Switzerland, 6–12 September 2014; Springer: Berlin/Heidelberg, Germany, 2014; pp. 834–849. [ Google Scholar ]
• Liang, H.J.; Sanket, N.J.; Fermüller, C.; Aloimonos, Y. Salientdso: Bringing attention to direct sparse odometry. IEEE Trans. Autom. Sci. Eng. 2019 , 16 , 1619–1626. [ Google Scholar ] [ CrossRef ]
• Klein, G.; Murray, D. Parallel tracking and mapping for small AR workspaces. In Proceedings of the 2007 6th IEEE and ACM International Symposium on Mixed and Augmented Reality, Nara, Japan, 13–16 November 2007; IEEE: Piscataway, NJ, USA, 2007; pp. 225–234. [ Google Scholar ]
• Rublee, E.; Rabaud, V.; Konolige, K.; Bradski, G. ORB: An efficient alternative to SIFT or SURF. In Proceedings of the 2011 International Conference on Computer Vision, Barcelona, Spain, 6–13 November 2011; IEEE: Piscataway, NJ, USA, 2011; pp. 2564–2571. [ Google Scholar ]
• Mur-Artal, R.; Montiel, J.M.M.; Tardos, J.D. ORB-SLAM: A versatile and accurate monocular SLAM system. IEEE Trans. Robot. 2015 , 31 , 1147–1163. [ Google Scholar ] [ CrossRef ]
• Newcombe, R.A.; Lovegrove, S.J.; Davison, A.J. DTAM: Dense tracking and mapping in real-time. In Proceedings of the 2011 International Conference on Computer Vision, Barcelona, Spain, 6–13 November 2011; IEEE: Piscataway, NJ, USA, 2011; pp. 2320–2327. [ Google Scholar ]
• Forster, C.; Zhang, Z.; Gassner, M.; Werlberger, M.; Scaramuzza, D. SVO: Semidirect visual odometry for monocular and multicamera systems. IEEE Trans. Robot. 2016 , 33 , 249–265. [ Google Scholar ] [ CrossRef ]
• Nishihta, S.; Maeyama, S.; Watanebe, K. Map generation in unknown environments by AUKF-SLAM using line segment-type and point-type landmarks. In Journal of Physics: Conference Series ; IOP Publishing: London, UK, 2018; Volume 962, p. 012018. [ Google Scholar ]
• Gomez-Ojeda, R.; Briales, J.; Gonzalez-Jimenez, J. PL-SVO: Semi-direct monocular visual odometry by combining points and line segments. In Proceedings of the 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, Republic of Korea, 9–14 October 2016; IEEE: Piscataway, NJ, USA, 2016; pp. 4211–4216. [ Google Scholar ]
• Pumarola, A.; Vakhitov, A.; Agudo, A.; Sanfeliu, A.; Moreno-Noguer, F. PL-SLAM: Real-time monocular visual SLAM with points and lines. In Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore, 29 May–3 June 2017; IEEE: Piscataway, NJ, USA, 2017; pp. 4503–4508. [ Google Scholar ]
• Yang, H.; Yuan, J.; Gao, Y.; Sun, X.; Zhang, X. UPLP-SLAM: Unified point-line-plane feature fusion for RGB-D visual SLAM. Inf. Fusion 2023 , 96 , 51–65. [ Google Scholar ] [ CrossRef ]
• Liu, X.; Wen, S.; Zhang, H. A Real-time Stereo Visual-Inertial SLAM System Based on Point-and-Line Features. IEEE Trans. Veh. Technol. 2023 , 72 , 5747–5758. [ Google Scholar ] [ CrossRef ]
• Shu, F.; Wang, J.; Pagani, A.; Stricker, D. Structure plp-slam: Efficient sparse mapping and localization using point, line and plane for monocular, rgb-d and stereo cameras. In Proceedings of the 2023 IEEE International Conference on Robotics and Automation (ICRA), London, UK, 29 May–2 June 2023; IEEE: Piscataway, NJ, USA, 2023; pp. 2105–2112. [ Google Scholar ]
• Xia, Y.; Wu, H.; Zhu, L.; Qi, W.; Zhang, S.; Zhu, J. A multi-sensor fusion framework with tight coupling for precise positioning and optimization. Signal Process. 2024 , 217 , 109343. [ Google Scholar ] [ CrossRef ]
• Xia, Y.; Cheng, J.; Cai, X.; Zhang, S.; Zhu, J.; Zhu, L. SLAM Back-End Optimization Algorithm Based on Vision Fusion IPS. Sensors 2022 , 22 , 9362. [ Google Scholar ] [ CrossRef ] [ PubMed ]
• Qi, W.; Xia, Y.; Zhang, S.; Zhang, S.; Zhu, L. Research on Stability-Enhanced Clustering Algorithm Based on Distributed Node Status Judgment in MWSN. Electronics 2022 , 11 , 3865. [ Google Scholar ] [ CrossRef ]
• Qi, W.; Xia, Y.; Zhu, P.; Zhang, S.; Zhu, L.; Zhang, S. Secure and efficient blockchain-based consensus scheme for MWSNs with clustered architecture. Pervasive Mob. Comput. 2023 , 94 , 101830. [ Google Scholar ] [ CrossRef ]
• Ye, K.; Dong, S.; Fan, Q.; Wang, H.; Yi, L.; Xia, F.; Wang, J.; Chen, B. Multi-robot active mapping via neural bipartite graph matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, New Orleans, LA, USA, 18–24 June 2022; pp. 14839–14848. [ Google Scholar ]
• Dong, H.; Yu, J.; Xu, Y.; Xu, Z.; Shen, Z.; Tang, J.; Shen, Y.; Wang, Y. MR-GMMapping: Communication efficient multi-robot mapping system via Gaussian mixture model. IEEE Robot. Autom. Lett. 2022 , 7 , 3294–3301. [ Google Scholar ] [ CrossRef ]
• Zhang, L.; Lin, Z.; Wang, J.; He, B. Rapidly-exploring Random Trees multi-robot map exploration under optimization framework. Robot. Auton. Syst. 2020 , 131 , 103565. [ Google Scholar ] [ CrossRef ]
• Zhang, Z.; Yu, J.; Tang, J.; Xu, Y.; Wang, Y. MR-TopoMap: Multi-robot exploration based on topological map in communication restricted environment. IEEE Robot. Autom. Lett. 2022 , 7 , 10794–10801. [ Google Scholar ] [ CrossRef ]
• Chang, Y.; Ebadi, K.; Denniston, C.E.; Ginting, M.F.; Rosinol, A.; Reinke, A.; Palieri, M.; Shi, J.; Chatterjee, A.; Morrell, B.; et al. LAMP 2.0: A robust multi-robot SLAM system for operation in challenging large-scale underground environments. IEEE Robot. Autom. Lett. 2022 , 7 , 9175–9182. [ Google Scholar ] [ CrossRef ]
• Ebadi, K.; Chang, Y.; Palieri, M.; Stephens, A.; Hatteland, A.; Heiden, E.; Thakur, A.; Funabiki, N.; Morrell, B.; Wood, S.; et al. LAMP: Large-scale autonomous mapping and positioning for exploration of perceptually-degraded subterranean environments. In Proceedings of the 2020 IEEE International Conference on Robotics and Automation (ICRA), Paris, France, 31 May–31 August 2020; IEEE: Piscataway, NJ, USA, 2020; pp. 80–86. [ Google Scholar ]
• Zhang, L.; Koch, R. An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency. J. Vis. Commun. Image Represent. 2013 , 24 , 794–805. [ Google Scholar ] [ CrossRef ]
• Wang, Z.; Wu, F.; Hu, Z. MSLD: A robust descriptor for line matching. Pattern Recognit. 2009 , 42 , 941–953. [ Google Scholar ] [ CrossRef ]
• Li, S.; Xu, C.; Xie, M. A robust O (n) solution to the perspective-n-point problem. IEEE Trans. Pattern Anal. Mach. Intell. 2012 , 34 , 1444–1450. [ Google Scholar ] [ CrossRef ] [ PubMed ]
• Angeli, A.; Filliat, D.; Doncieux, S.; Meyer, J.A. Fast and incremental method for loop-closure detection using bags of visual words. IEEE Trans. Robot. 2008 , 24 , 1027–1037. [ Google Scholar ] [ CrossRef ]
• Umeyama, S. Least-squares estimation of transformation parameters between two point patterns. IEEE Trans. Pattern Anal. Mach. Intell. 1991 , 13 , 376–380. [ Google Scholar ] [ CrossRef ]

Click here to enlarge figure

Share and Cite

Xia, Y.; Wu, X.; Ma, T.; Zhu, L.; Cheng, J.; Zhu, J. Multi-Robot Collaborative Mapping with Integrated Point-Line Features for Visual SLAM. Sensors 2024 , 24 , 5743. https://doi.org/10.3390/s24175743

Xia Y, Wu X, Ma T, Zhu L, Cheng J, Zhu J. Multi-Robot Collaborative Mapping with Integrated Point-Line Features for Visual SLAM. Sensors . 2024; 24(17):5743. https://doi.org/10.3390/s24175743

Xia, Yu, Xiao Wu, Tao Ma, Liucun Zhu, Jingdi Cheng, and Junwu Zhu. 2024. "Multi-Robot Collaborative Mapping with Integrated Point-Line Features for Visual SLAM" Sensors 24, no. 17: 5743. https://doi.org/10.3390/s24175743

Article Metrics

Article access statistics, further information, mdpi initiatives, follow mdpi.

Subscribe to receive issue release notifications and newsletters from MDPI journals

IEEE Account

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

This week: the arXiv Accessibility Forum

Help | Advanced Search

Computer Science > Robotics

Title: a framework for training and benchmarking algorithms that schedule robot tasks.

Abstract: Service robots work in a changing environment habited by exogenous agents like humans. In the service robotics domain, lots of uncertainties result from exogenous actions and inaccurate localisation of objects and the robot itself. This makes the robot task scheduling problem incredibly challenging. In this article, we propose a benchmarking system for systematically assessing the performance of algorithms scheduling robot tasks. The robot environment incorporates a room map, furniture, transportable objects, and moving humans; the system defines interfaces for the algorithms, tasks to be executed, and evaluation methods. The system consists of several tools, easing testing scenario generation for training AI-based scheduling algorithms and statistical testing. For benchmarking purposes, a set of scenarios is chosen, and the performance of several scheduling algorithms is assessed. The system source is published to serve the community for tuning and comparable assessment of robot task scheduling algorithms for service robots.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .