No Access

MULTIDIMENSIONAL ONLINE MOTION PLANNING FOR A SPHERICAL ROBOT

JOSH BROWN KRAMER

Department of Mathematics and Computer Science, Illinois Wesleyan University, Bloomington IL 61701, USA

Search for more papers by this author

and

LUCAS SABALKA

Department of Mathematical Sciences, Binghamton University, Binghamton NY 13902-6000, USA

Search for more papers by this author

https://doi.org/10.1142/S0218195910003475Cited by:1 (Source: Crossref)

Abstract

We consider three related problems of robot movement in arbitrary dimensions: coverage, search, and navigation. For each problem, a spherical robot is asked to accomplish a motion-related task in an unknown environment whose geometry is learned by the robot during navigation. The robot is assumed to have tactile and global positioning sensors. We view these problems from the perspective of (non-linear) competitiveness as defined by Gabriely and Rimon. We first show that in 3 dimensions and higher, there is no upper bound on competitiveness: every online algorithm can do arbitrarily badly compared to the optimal. We then modify the problems by assuming a fixed clearance parameter. We are able to give optimally competitive algorithms under this assumption. We show that these modified problems have polynomial competitiveness in the optimal path length, of degree equal to the dimension.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

R. A. Baeza-Yates, J. C. Culberson and G. J. E. Rawlins, Inform. and Comput. 106(2), 234 (1993). Crossref, Web of Science, Google Scholar
P. Berman, Online algorithms, Lecture Notes in Comput. Sci. 1442 (Springer, Berlin, 1998) pp. 232–241. Crossref, Google Scholar
A. Blum, P. Raghavan and B. Schieber, SIAM J. Comput. 26(1), 110 (1997), DOI: 10.1137/S0097539791194931. Crossref, Web of Science, Google Scholar
D. G. Caraballo, Pacific J. Math. 218(1), 37 (2005), DOI: 10.2140/pjm.2005.218.37. Crossref, Web of Science, Google Scholar
J. Carsten et al. , Global path planning on-board the mars exploration rovers , IEEE Aerospace Conf. . Google Scholar
A. Fiat and G. J. Woeginger (eds.) , Online Algorithms: The State of the Art , Lecture Notes in Computer Science 1442 ( Springer-Verlag , Berlin , 1998 ) . Crossref, Google Scholar
Y. Gabriely and E. Rimon, IEEE Trans. Robot. Autom. 6, 1451 (2008). Google Scholar
C. Ickinget al., Sensor Based Intelligent Robots, Lecture Notes in Computer Science 2238 (Springer Verlag, 2002) pp. 245–258. Crossref, Google Scholar
C. Icking and R. Klein, Modelling and Planning for Sensor Based Intelligent Robot Systems, eds. H. Bunke, T. Kanade and H. Noltemeier (World Scientific, Singapore, 1995) pp. 23–40. Link, Google Scholar
L. E. Kavraki, M. N. Kolountzakis and J.-C. Latombe, IEEE Trans. Robot. Autom. 14(1), 166 (1998), DOI: 10.1109/70.660866. Crossref, Google Scholar
J. C. Latombe , Robot Motion Planning ( Kluwer Academic , Boston, MA , 1991 ) . Crossref, Google Scholar
S. Lavalle , Planning Algorithms ( Cambridge University Press , 2006 ) . Crossref, Google Scholar
V. J. Lumelsky and A. A. Stepanov, Algorithmica 2(4), 403 (1987), DOI: 10.1007/BF01840369. Crossref, Web of Science, Google Scholar
C. H. Papadimitriou and M. Yannakakis, Theoret. Comput. Sci. 84, 127 (1991), DOI: 10.1016/0304-3975(91)90263-2. Crossref, Web of Science, Google Scholar
D. D. Sleator and R. E. Tarjan, Comm. ACM 28(2), 202 (1985), DOI: 10.1145/2786.2793. Crossref, Web of Science, Google Scholar