Carnegie Mellon University
The
The Feasible Transition Graph: Encoding Topology and Manipulation Constraints for Multirobot Push-Planning

Laura Lindzey, Ross Alan Knepper, Howie Choset, and Siddhartha Srinivasa
The Eleventh International Workshop on the Algorithmic Foundations of Robotics (WAFR), August, 2014.


Download
  • Adobe portable document format (pdf) (255KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
Planning for multirobot manipulation in dense clutter becomes partic- ularly challenging as the motion of the manipulated object causes the connectiv- ity of the robots’ free space to change. This paper introduces a data structure, the Feasible Transition Graph (FTG), and algorithms that solve such complex motion planning problems. We define an equivalence relation over object configurations based on the robots’ free space connectivity. Within an equivalence class, the ho- mogeneous multirobot motion planning problem is straightforward, which allows us to decouple the problems of composing feasible object motions and planning paths for individual robots. The FTG captures transitions among the equivalence classes and encodes constraints that must be satisfied for the robots to manipulate the object. From this data structure, we readily derive a complete planner to coor- dinate such motion. Finally, we show how to construct the FTG in some sample environments and discuss future adaptations to general environments.

Notes

Text Reference
Laura Lindzey, Ross Alan Knepper, Howie Choset, and Siddhartha Srinivasa, "The Feasible Transition Graph: Encoding Topology and Manipulation Constraints for Multirobot Push-Planning," The Eleventh International Workshop on the Algorithmic Foundations of Robotics (WAFR), August, 2014.

BibTeX Reference
@inproceedings{Lindzey_2014_7675,
   author = "Laura Lindzey and Ross Alan Knepper and Howie Choset and Siddhartha Srinivasa",
   title = "The Feasible Transition Graph: Encoding Topology and Manipulation Constraints for Multirobot Push-Planning",
   booktitle = "The Eleventh International Workshop on the Algorithmic Foundations of Robotics (WAFR)",
   month = "August",
   year = "2014",
}