Organization Of Randomized Movable Obstacles

Infantdani Abel Rayan, Sethumadhavan Narayanaswamy, Evan Seguin, Hyun-Soo Yi

Project Abstract:

For our project, we propose a planner that will organize an environment full of tightly clustered movable obstacles. Each object will have a desired location and orientation that may or may not be obstructed by another object. It will be the goal of our planner to determine a course of actions that will lead to a fully organized environment. To demonstrate this, we will use the well defined structure of chess pieces on a chess board. Our problem will begin with a pile of chess pieces in random locations and orientations, and it will be the task of our planner to determine a way in which all pieces can be returned to their proper location.

Related Work:

  • J. van den Berg, M. Stilman, J. Kuffner, M. Lin, D. Manocha. "Path Planning among Movable Obstacles: a Probabilistically Complete Approach." Proc. Workshop on Algorithmic Foundation of Robotics - WAFR'08, 2008. - This paper describes a probabilistically complete navigation algorithm for a robot in an environment with both movable and static obstacles. In our project, instead of obstacles we have static (chess board) and movable (chess pieces) objects. Instead of navigation, we need to rearrange the chess pieces. Despite these differences, the parts about the object manipulation remains the same.
  • J. Ota, "Rearrangement planning of multiple movable objects by using real-time search methodology", Robotics and Automation, 2002. Proceedings. ICRA apos;02. IEEE International Conference on Volume 1, Issue , 2002 Page(s): 947 - 953 vol.1. - This paper describes the problem of rearrangement of objects using a mobile robot and gives a solution using Learning Real Time A* (LRTA*) search methodology. Our chess problem is in effect a rearrangement planning problem, though instead of a mobile robot we use a robot hand for manipulating the objects (chess pieces).
  • Lowe, D. G., “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, 60, 2, pp. 91-110, 2004. - This paper describes the Scale Invariant Feature Transform (SIFT) algorithm. This algorithm is widely used in computer vision for feature detection, and can be used for object recognition tasks. We plan to use it to be able to uniquely identify chess pieces in a cluttered environment. This algorithm has been used and tested extensively, and will allow us to identify different chess pieces (relatively) easily.
  • Steven M. Lavalle , James J. Kuffner , Jr. "Rapidly-Exploring Random Trees: Progress and Prospects (2000)", Workshop on Algorithmic Foundations of Robotics, (Dartmouth, NH), Mar 2000 - Arranging chess pieces is a planning problem that involves Holonomic constraints for rigid and articulated bodies. The Holonomic Planning experiments presented in this paper proves that RRT based solution is very efficient since it attempts to find a solution without performing pre-computations in entire state space and is well suited for single query path planning problems. One of the experiment in this paper, involves a human character playing chess, each of the motions necessary to reach, grasp and reposition a game piece on virtual chess board was generated using RRT-ExtCon Planner and 7-DOF kinematic chain human arm.
  • Andrew T. Miller, Steffen Knoop, Henrik I. Christensen, and Peter K. Allen. "Automatic grasp planning using shape primitives". In Proc. IEEE Intl. Conference on Robotics and Automation, pages 1824–1829, 2003. - This paper deals with grasp motions with a robot's hand. It simplifies complicate objects into simple shape primitives such as spheres, cylinders, corns, and boxes to perform automatic grasp. With this idea, we can simplify chess pieces to cylinder shapes. Thus, it makes our takes simpler to grasp chess pieces.

Proposed Work:

Planning Challenges
What about your problem makes it interesting from the perspective of planning. What challenges will you encounter that basic planners / motion planners / controllers do not address.
  • reconfigurable action planning: We will have to develop a planner that can pick up a chess piece in an arbitrary orientation and stand it upright at a destination. A major challenge to this will be dealing with goals that are unreachable from specific grasps. For example, the planner may need to pick the piece up, set it upright at a free location, and then re-grasp it in such a way that it is now able to develop a plan that will deliver it to the target location.
  • manipulating movable obstacles: Our environment will contain a number of obstacles (chess pieces) that can be moved and re-oriented. Our planner will have to be able to recognize the constraints that these objects place in the workspace and leverage their mobility in order to create successful plans.
Proposed Solutions
How will your work address these challenges. Be as specific as possible
  • To address the first challenge, we plan to expand an RRT for a fixed number of iterations to see if a plan can be found to bring a piece from its current state to its upright, goal state. If no plan can be devised, we will attempt to set the piece upright and then re-grasp it. From there, we will expand another RRT to find an appropriate plan.
  • To address the second challenge, we will explicitly maintain the robot hand's free configuration space as well as the configuration space of all the chess pieces. The pieces are moved only if they remain manipulable and collision free throughout the duration of the movement. We keep track of the robot hand's free configuration space throughout the duration of the movement.
Implementation Challenges
What other problems do you expect to face in your implementation? Will you need some kind of robot hardware / software / sensors? Will you need to solve any problems in addition to planning.
  • robotic hand grasping: Our lab's hand has the ability to grasp objects, but no library for doing so has been developed yet
  • vision/object recognition: We will need to use computer vision to classify chess pieces and determine their orientation
Proposed Solutions
What algorithms will be required to make these tools useful to your planner? How will you acquire them / implement them?
  • Our goal is to simplify these problems as much as possible, as they are not directly relevant to the problem we want to address. The problem of grasping an object can be made very complicated, but we plan to exploit the mostly regular shapes of chess pieces and grasp simply by closing all 3 fingers until a certain threshold of pressure is achieved, at which point the object should be firmly grasped.
  • To handle vision and object recognition, our code will contain some prior knowledge of each piece. We haven't decided exactly which method to use, but for now we're considering two options. One option is to put small stickers on each piece of different colors (i.e. knights have green stickers) so that we can easily identify which pieces are which without any serious computer vision. Another option is to store SIFT feature descriptors of each piece, and then calculate the descriptors for every piece that the arm grasps. With some amount of tweaking and manipulation, we believe that this option is equally feasible. Whether or not it is worth the additional time spent is to be decided.


General Task Dani Sethu Hyun-Soo Evan
Week 1 Get project ready to present. Research references Research references Make ppt for Tuesday Prepare this page
Week 2 Develop basic motion planner and grasping library RRT path optimization manipulation manipulation
Week 3 Basic working planner in simulator RRT path optimization manipulation manipulation
Week 4 Grasping a single piece using vision and robot arm Planner for arm movement Optimization of Plans Grasping: hand movement Vision: object recognition
Week 5 Picking up fallen piece from board and placing in proper location
Week 6 Working planner with obstacles
Week 7 Paper writing & overflow
Week 8 Paper writing & finalization

Week 1

This week we basically ditched our old project and worked to develop a new one. Once we agreed upon this one, we researched the topic, filled out this page, and prepared our presentation. Parallel to that, we worked to develop stable arm code and looked into chess pieces of various sizes to purchase. Not to mention project 2.

Week 2

This week we worked on project 2 without our final project components. We separated the project into parts and we individually

Week 3

This week we customized RST to fit our final project. We added a chess board and pieces into RST and able to grasp a chess piece and move it to right position.

Video of the arm moving a chess piece:

Week 4

Week 5

Week 6

Week 7

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License

Subscription expired — please renew

Pro account upgrade has expired for this site and the site is now locked. If you are the master administrator for this site, please renew your subscription or delete your outstanding sites or stored files, so that your account fits in the free plan.