Invariants for homology classes with application to optimal search and planning problem in robotics

DOI10.1007/S10472-013-9357-7zbMATH Open1282.94015arXiv1208.0573OpenAlexW2094827274MaRDI QIDQ360246FDOQ360246

Vijay Kumar, David Lipsky, Robert Ghrist, Subhrajit Bhattacharya

Publication date: 26 August 2013

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Abstract: We consider planning problems on a punctured Euclidean spaces, $mathbb{R}^D-widetildemathcalO$, where $widetildemathcalO$ is a collection of obstacles. Such spaces are of frequent occurrence as configuration spaces of robots, where $widetildemathcalO$ represent either physical obstacles that the robots need to avoid (e.g., walls, other robots, etc.) or illegal states (e.g., all legs off-the-ground). As state-planning is translated to path-planning on a configuration space, we collate equivalent plannings via topologically-equivalent paths. This prompts finding or exploring the different homology classes in such environments and finding representative optimal trajectories in each such class. In this paper we start by considering the problem of finding a complete set of easily computable homology class invariants for $(N-1)$-cycles in $(mathbb{R}^D-widetildemathcalO)$. We achieve this by finding explicit generators of the $(N-1{)}^{st}$ de Rham cohomology group of this punctured Euclidean space, and using their integrals to define cocycles. The action of those dual cocycles on $(N-1)$-cycles gives the desired complete set of invariants. We illustrate the computation through examples. We further show that, due to the integral approach, this complete set of invariants is well-suited for efficient search-based planning of optimal robot trajectories with topological constraints. Finally we extend this approach to computation of invariants in spaces derived from $(mathbb{R}^D-widetildemathcalO)$ by collapsing subspace, thereby permitting application to a wider class of non-Euclidean ambient spaces.

Full work available at URL: https://arxiv.org/abs/1208.0573

Recommendations

• Path homotopy invariants and their application to optimal trajectory planning
• Path homotopy invariants and their application to optimal trajectory planning
• Configuration spaces and robot motion planning algorithms
• Topology and Robotics
• Topology of robot motion planning

zbMATH Keywords

cohomologyconfiguration spacehomologypath planning

Mathematics Subject Classification ID

Singular homology and cohomology theory (55N10) Artificial intelligence for robotics (68T40) Automated systems (robots, etc.) in control theory (93C85) Modulation and demodulation in information and communication theory (94A14)

Cites Work

• Topology and data
• Computational topology. An introduction
• Title not available (Why is that?)
• Barcodes: The persistent topology of data
• Introduction to algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational homology
• Title not available (Why is that?)
• Title not available (Why is that?)
• Topology and the robot arm
• Lectures on algebraic topology.
• Topological dynamics: rigorous numerics via cubical homology
• Nonpositive Curvature and Pareto Optimal Coordination of Robots
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Safe Cooperative Robot Dynamics on Graphs
• Title not available (Why is that?)

Cited In (1)

• Path homotopy invariants and their application to optimal trajectory planning

Uses Software

• Armadillo
• GSL
• YAGSBPL
• Algorithm 145

This page was built for publication: Invariants for homology classes with application to optimal search and planning problem in robotics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q360246)