Feasibility of motion planning on acyclic and strongly connected directed graphs

DOI10.1016/J.DAM.2010.02.001MaRDI QIDQ708329zbMATH OpenOpenAlexFDO

Authors Zhilin Wu, Stéphane Grumbach

Publication date 11 October 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.02.001

zbMATH Keywords

motion planningfeasibilityacyclic directed graphsstrongly connected directed graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Artificial intelligence for robotics (68T40)

Recommendations

• Feasibility of Motion Planning on Directed Graphs
• Graphbots: mobility in discrete spaces
• Reducing Multiple Object Motion Planning to Graph Searching
• On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems
• scientific article; zbMATH DE number 4108220

Cites work

• scientific article; zbMATH DE number 1306881 (Why is no real title available?)
• scientific article; zbMATH DE number 2200042 (Why is no real title available?)
• A linear time algorithm for the feasibility of pebble motion on trees
• Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard
• Graph puzzles, homotopy, and the alternating group
• Introduction to algorithms
• Optimal pebble motion on a tree
• Planning Algorithms

Cited in

(11)

• On reachability in graphs with obstacles
• Backtracking problem in the traversal of an unknown directed graph by a finite robot
• On Complete S-Reachable Graphs
• Graphbots: mobility in discrete spaces
• The computational complexity of multi-agent pathfinding on directed graphs
• Feasibility of Motion Planning on Directed Graphs
• On \(m\)RJ reachability in trees
• A characterization of biconnected graphs reachable by robots jumping over \(m\) obstacles
• Minimum 2-vertex strongly biconnected spanning directed subgraph problem
• Introduction to reconfiguration
• Constrained motion planning and multi-agent path finding on directed graphs

This page was built for publication: Feasibility of motion planning on acyclic and strongly connected directed graphs

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