Conference proceeding
Lazy robots constrained by at most two polygons
2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp 2762-2767
2005
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We present a polynomial-time algorithm for a special case of the Euclidean traveling salesman problem in which a robot must visit all the vertices of two non-intersecting polygons without crossing any polygon edge. If both polygons are convex, one enclosing the other, our algorithm can find the optimal tour of the channel between them in time O(m/sup 3/ + m/sup 2/n) and O(nm + m/sup 2/) space, where the exterior polygon has n vertices and the interior m vertices. In the more general case of non-convex polygons (not necessarily nested), the algorithm finds the exact optimum tour in O(n/sup 2/m + m/sup 3/) time and O(n/sup 2/ + m/sup 2/) space. At the end we give several examples in the context of robot navigation.
Metrics
Details
- Title
- Lazy robots constrained by at most two polygons
- Creators
- J Abrahamson - Drexel UniversityA Shokoufandeh - Drexel UniversityIEEE
- Publication Details
- 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp 2762-2767
- Publisher
- IEEE
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000235632100098
- Scopus ID
- 2-s2.0-79957999147
- Other Identifier
- 991019168466704721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Artificial Intelligence
- Robotics