Sage Journals: Discover world-class research

Abstract

We present a new roadmap based on a generalized Voronoi graph for two-identical-link mobile robots to explore an unknown planar environment. It is called the L²-generalized Voronoi graph and is defined in terms of workspace distance measurements using only sensor-provided information, with the robot having the maximum distance from obstacles, and is therefore optimum in a point of view for exploration and obstacle avoidance. The configuration of the robot possesses four degrees of freedom, and hence the roadmap is one-dimensional in an unknown configuration space $ℝ 2 \times T 2$ . The L²-generalized Voronoi graph is not always connected, and so is connected with an additional structure called the L²R-edge, where the robot is tangent to a GVD structure with the same orientation for the two links. This roadmap is termed L² hierarchical generalized Voronoi graph. The L² hierarchical generalized Voronoi graph includes two structures: the L² hierarchical generalized Voronoi graph and the L²R edge. Although the condition of two identical links looks somewhat constraining, the L² hierarchical generalized Voronoi graph is still worth pursuing because the case is very common in the engineering environment.

Keywords

Two-identical-link mobile robots sensor-based path planning hierarchical generalized Voronoi graph

Get full access to this article

View all access options for this article.

References

Canny

. The complexity of robot motion planning, Cambridge, MA: MIT Press, 1988.

Canny

Lin

. An opportunistic global path planner. Algorithmica 1993; 10: 102–120.

Rimon E and Canny JF. Construction of c-space roadmaps using local sensory data—what should the sensors look for? In: International conference on robotics and automation, San Diego, CA, 1994, pp.117–124.

Ó’Dúnlaing

Yap

. A “retraction” method for planning the motion of a disc. J Algorithms 1985; 6: 104–111.

Nagatani K and Choset H. Toward robust sensor based exploration by constructing reduced generalized Voronoi graph. In: IEEE/RSJ international conference on intelligent robots and systems, Kyongju, Korea, 1999, pp.1687–1692. New York, USA: IEEE.

Colunga

Bradley

. Modelling of transient cornering and suspension dynamics, and investigation into the control strategies for an ideal driver in a lap time simulator. Proc IMechE, Part D: J Automobile Engineering 2014; 228: 1185–1199.

Nagatani

Iwai

Tanaka

. Sensor based navigation for car-like mobile robots using generalized Voronoi. Adv Robotics 2003; 17: 385–401.

Choset H and Burdick J. Sensor based planning. I. The generalized Voronoi graph. In: IEEE international conference on robotics and automation, Nagoya, Japan, May 1995, pp.1649–1655. New York, USA: IEEE.

Choset H and Burdick J. Sensor based planning, part ii: incremental construction of the generalized voronoi graph. In: IEEE international conference on robotics and automation, Nagoya, Japan, May 1995, pp.1643–1643. New York, USA: IEEE.

10.

Choset

Burdick

. Sensor-based exploration: the hierarchical generalized Voronoi graph. Int J Robotics Res 2000; 19: 96–125.

11.

Choset

Burdick

. Sensor based motion planning: incremental construction of the hierarchical generalized Voronoi graph. Int J Robotics Res 2000; 19: 126–148.

12.

Hoff KE III, Keyser J, Lin M, et al. Fast computation of generalized voronoi diagrams using graphics hardware. In: Proceedings of the 26th annual conference on Computer graphics and interactive techniques, 1999, pp.277–286. New York, USA: ACM Press/Addison-wesley.

13.

Hoff KE III, Culver T, Keyser J, et al. Interactive motion planning using hardware-accelerated computation of generalized voronoi diagrams. In: Proceedings. ICRA’00. IEEE international conference on robotics and automation, San Francisco, CA USA, April 2000, volume 3, pp.2931–2937. New York, USA: IEEE.

14.

Pisula C, Hoff K, Lin M, et al. Randomized path planning for a rigid body based on hardware accelerated voronoi sampling. In: Proc. workshop on algorithmic foundation of robotics, volume 18, Cite-seer, 2000. New York, USA: IEEE.

15.

Foskey M, Garber M, Lin MC, et al. A voronoi-based hybrid motion planner. In: Proceedings. 2001 IEEE/RSJ international conference on intelligent robots and systems, Hawaii, USA, 2001, volume 1, pp.55–60. New York, USA: IEEE.

16.

Choset

Lee

. Sensor-based construction of a retract-like structure for a planar rod robot. IEEE Trans Robot Autom 2001; 17: 435–449.

17.

Lee

Choset

. Sensor based planning for rod shaped robots in three dimensions: piece-wise retracts of R³× S². Int J Robot Res 2005; 24: 343–383.

18.

Lee JY and Choset H. Sensor-based exploration for convex-bodies: a new roadmap for a convex-shaped robot. In: IEEE international conference on robotics and automation, Washington DC, USA, May 2002, pp.1675–1682. New York, USA: IEEE.

19.

Hatton

Choset

. Generating gaits for snake robots: annealed chain fitting and keyframe wave extraction. Autonomous Robots 2010; 28: 271–281.

20.

Rembisz

Choset

. Parameterized and scripted gaits for modular snake robots. Adv Robot 2009; 23: 1131–1158.

21.

Choset

Lynch

Hutchinson

. Principles of robot motion: theory, algorithms, and implementations, Cambridge, MA: MIT Press, 2005.

22.

Choset H, Konukseven I and Rizzi A. Sensor based planning: a control law for generating the generalized Voronoi graph. In: Eighth international conference on advanced robotics, Monterey, CA, 7–9 July 1997, pp.333–338. New York, USA: IEEE.

23.

Choset H, Konuksven I and Burdick J. Mobile robot navigation: issues in implementing the generalized Voronoi graph in the plane. In: IEEE/SICE/RSJ international conference on multisensor fusion and integration for intelligent systems, New York, 1996, pp.241–248. New York, USA: IEEE.

Sensor-based exploration for planar two-identical-link robots

Abstract

Keywords

Get full access to this article

References