Walking in streets with minimal sensing

Azadeh Tabatabaei () and Mohammad Ghodsi ()
Additional contact information
Azadeh Tabatabaei: Sharif University of Technology
Mohammad Ghodsi: Sharif University of Technology

Journal of Combinatorial Optimization, 2015, vol. 30, issue 2, No 12, 387-401

Abstract: Abstract We consider the problem of walking a robot in an unknown polygon called “street”, starting from a point $$s$$ s to reach a target $$t$$ t . The robot is assumed to have minimal sensing capability in a way that cannot infer any geometric properties of the environment, such as its coordinates, angles or distances; but it is equipped with a sensor that can only detect the discontinuities in the depth information (or gaps). Our robot can also locate the target point $$t$$ t as soon as it enters in robot’s visibility region. In addition, one pebble is assumed to be available to the robot to be used as an identifiable point and to mark any position of the street. Our goal is to generate a shortest possible path for such robot from $$s$$ s to $$t$$ t in such a scene. We offer a data structure similar to Gap Navigation Tree to maintain the essential sensed data of the explored street. We present an online strategy that guides our robot to navigate the scene and reach the target. The strategy is based only on what is sensed at each point, and on what is saved in the data structure. Although the robot has a limited capability, we show that the robot’s detour from the shortest path can be restricted such that our generated path is at most 11 times as long as the shortest path to the target. We also consider a special case of the problem in which the street is rectilinear and the search path has to be rectilinear. We propose a search strategy for this case that generates an $$L_1$$ L 1 -shortest path from $$s$$ s to $$t$$ t .

Keywords: Computational geometry; Robotics; Minimal sensing; Online algorithms; Competitive ratio (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9791-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:2:d:10.1007_s10878-014-9791-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9791-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().