Cargando…

A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments

This work presents a heuristic for describing the next best view location for an autonomous agent exploring an unknown environment. The approach considers each robot as a point mass with omnidirectional and unrestricted vision of the environment and line-of-sight communication operating in a polygon...

Descripción completa

Detalles Bibliográficos
Autores principales: Graves, Russell, Chakraborty, Subhadeep
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Frontiers Media S.A. 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7805636/
https://www.ncbi.nlm.nih.gov/pubmed/33500906
http://dx.doi.org/10.3389/frobt.2018.00019
_version_ 1783636345002917888
author Graves, Russell
Chakraborty, Subhadeep
author_facet Graves, Russell
Chakraborty, Subhadeep
author_sort Graves, Russell
collection PubMed
description This work presents a heuristic for describing the next best view location for an autonomous agent exploring an unknown environment. The approach considers each robot as a point mass with omnidirectional and unrestricted vision of the environment and line-of-sight communication operating in a polygonal environment which may contain holes. The number of robots in the team is always sufficient for full visual coverage of the space. The technique employed falls in the category of distributed visibility-based deployment algorithms which seek to segment the space based on each agent’s field of view with the goal of deploying each agent into the environment to create a visually connected series of agents which fully observe the previously unknown region. The contributions made to this field are a technique for utilizing linear programming methods to determine the solution to the next best observation (NBO) problem as well as a method for calculating multiple NBO points simultaneously. Both contributions are incorporated into an algorithm and deployed in a simulated environment built with MATLAB for testing. The algorithm successfully deployed agents into polygons which may contain holes. The efficiency of the deployment method was compared with random deployment methods to establish a performance metric for the proposed tactic. It was shown that the heuristic presented in this work performs better the other tested strategies.
format Online
Article
Text
id pubmed-7805636
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Frontiers Media S.A.
record_format MEDLINE/PubMed
spelling pubmed-78056362021-01-25 A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments Graves, Russell Chakraborty, Subhadeep Front Robot AI Robotics and AI This work presents a heuristic for describing the next best view location for an autonomous agent exploring an unknown environment. The approach considers each robot as a point mass with omnidirectional and unrestricted vision of the environment and line-of-sight communication operating in a polygonal environment which may contain holes. The number of robots in the team is always sufficient for full visual coverage of the space. The technique employed falls in the category of distributed visibility-based deployment algorithms which seek to segment the space based on each agent’s field of view with the goal of deploying each agent into the environment to create a visually connected series of agents which fully observe the previously unknown region. The contributions made to this field are a technique for utilizing linear programming methods to determine the solution to the next best observation (NBO) problem as well as a method for calculating multiple NBO points simultaneously. Both contributions are incorporated into an algorithm and deployed in a simulated environment built with MATLAB for testing. The algorithm successfully deployed agents into polygons which may contain holes. The efficiency of the deployment method was compared with random deployment methods to establish a performance metric for the proposed tactic. It was shown that the heuristic presented in this work performs better the other tested strategies. Frontiers Media S.A. 2018-03-07 /pmc/articles/PMC7805636/ /pubmed/33500906 http://dx.doi.org/10.3389/frobt.2018.00019 Text en Copyright © 2018 Graves and Chakraborty. http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) and the copyright owner are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.
spellingShingle Robotics and AI
Graves, Russell
Chakraborty, Subhadeep
A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments
title A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments
title_full A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments
title_fullStr A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments
title_full_unstemmed A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments
title_short A Linear Objective Function-Based Heuristic for Robotic Exploration of Unknown Polygonal Environments
title_sort linear objective function-based heuristic for robotic exploration of unknown polygonal environments
topic Robotics and AI
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7805636/
https://www.ncbi.nlm.nih.gov/pubmed/33500906
http://dx.doi.org/10.3389/frobt.2018.00019
work_keys_str_mv AT gravesrussell alinearobjectivefunctionbasedheuristicforroboticexplorationofunknownpolygonalenvironments
AT chakrabortysubhadeep alinearobjectivefunctionbasedheuristicforroboticexplorationofunknownpolygonalenvironments
AT gravesrussell linearobjectivefunctionbasedheuristicforroboticexplorationofunknownpolygonalenvironments
AT chakrabortysubhadeep linearobjectivefunctionbasedheuristicforroboticexplorationofunknownpolygonalenvironments