Identification and Representation of Homotopy Classes of Trajectories for Search-based Path Planning in 3D

By Subhrajit Bhattacharya, Maxim Likhachev, Vijay R. Kumar. 2011

59 citations recorded by the source corpus.

There are many applications in motion planning where it is important to consider and distinguish between different homotopy classes of trajectories. Two trajectories are homotopic if one trajectory can be continuously deformed into another without passing through an obstacle, and a homotopy class is a collection of homotopic trajectories. In this paper we consider the problem of robot exploration and planning in three-dimensional configuration spaces to (a) identify and classify different homotopy classes; and (b) plan trajectories constrained to certain homotopy classes or avoiding specified homotopy classes. In previous work [1] we have solved this problem for two-dimensional, static environments using the Cauchy Integral Theorem in concert with graph search techniques. The robot workspace is mapped to the complex plane and obstacles are poles in this plane. The Residue Theorem allows the use of integration along the path to distinguish between trajectories in different homotopy classes. However, this idea is fundamentally limited to two dimensions. In this work we develop new techniques to solve the same problem, but in three dimensions, using theorems from electromagnetism. The Biot-Savart law lets us design an appropriate vector field, the line integral of which, using the integral form of Ampere’s Law, encodes information about homotopy classes in three dimensions. Skeletons of obstacles in the robot world are extracted and are modeled by currentcarrying conductors. We describe the development of a practical graph-search based planning tool with theoretical guarantees by combining integration theory with search techniques, and illustrate it with examples in three-dimensional spaces such as two-dimensional, dynamic environments and three-dimensional static environments. 1

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Control and Systems Engineering, Robotics & Control

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

In Robotics & Control

Citations in the corpus

Learning Trajectory Preferences for Manipulators via Iterative Improvement (2013, neutral): “Previously both approaches [2, 5, 6, 8, 33] have been studied.”
Learning preferences for manipulation tasks from online coactive feedback (2015, background): “Two effective ways of solving the former problem are either discretizing the state space (Alterovitz et al., 2007; Bhattacharya et al., 2011; Vernaza and Bagnell, 2012) or directly sampling trajectories from the continuous space (Berg et al.”