Afficher la notice abrégée

Worst-case optimal exploration of terrains with obstacles

hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorCZYZOWICZ, Jurek
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierCombinatoire et Algorithmique
dc.contributor.authorILCINKAS, David
hal.structure.identifierLaboratoire d'informatique Fondamentale de Marseille [LIF]
dc.contributor.authorLABOUREL, Arnaud
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorPELC, Andrzej
dc.date.accessioned2024-04-15T09:42:57Z
dc.date.available2024-04-15T09:42:57Z
dc.date.created2012-11-01
dc.date.issued2013-04-01
dc.identifier.issn0890-5401
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197723
dc.description.abstractEnA mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q is at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity View the MathML source, where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity View the MathML source, where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains (if one of the parameters A or k is known) or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain T with obstacles is c-fat if R/r⩽c, where R is the radius of the smallest disc containing T and r is the radius of the largest disc contained in T.) We also prove a matching lower bound View the MathML source on the complexity of exploration for limited vision, even if the terrain is known to the robot.
dc.language.isoen
dc.publisherElsevier
dc.subjectMobile robot
dc.subjectExploration
dc.subjectPolygon
dc.subjectObstacle
dc.title.enWorst-case optimal exploration of terrains with obstacles
dc.typeArticle de revue
dc.identifier.doi10.1016/j.ic.2013.02.001
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalInformation and Computation
bordeaux.page16-28
bordeaux.volume225
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00863496
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00863496v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Information%20and%20Computation&rft.date=2013-04-01&rft.volume=225&rft.spage=16-28&rft.epage=16-28&rft.eissn=0890-5401&rft.issn=0890-5401&rft.au=CZYZOWICZ,%20Jurek&ILCINKAS,%20David&LABOUREL,%20Arnaud&PELC,%20Andrzej&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée