The motion planning problem consists of finding a valid path between a start and a goal configuration for a movable object (the robot). Approximate methods for motion planning have been studied to overcome the intractability of the problem. Several randomized techniques produce a data structure (usually a graph or roadmap) that represents the connectivity of the space of valid robot configurations (free C-space). Ideally, a roadmap should have connected components that represent the connectivity of the free C-space (C-free) which implies it needs samples (roadmap nodes) in all distinct regions of C-free.
Although Randomized Motion Planners perform well on most of the problems, there still exist some problems that are beyond the capabilities of random motion planners (due to computational or time limitations). It is true that automatic methods are very good at computations which human operators find cumbersome and/or overly time consuming, e.g., detailed computations necessary to fully determine a continuous path. However, they sometimes fail to discover some `critical' configurations which leads a solution. In contrast, such configurations are often naturally apparent to a human observer.
We consider how to incorporate the strengths of both human operators and automatic planning methods. We propose two approaches: to use an interactive 3D visualization tool and to use a haptic interface.

VIZMO++

Haptic

• Visualization

  ---

  User-Guided Path Planning
  supported by NSF
  Marco A. Morales, Samuel Rodriguez, Nancy M. Amato
  Project Alumni: Aimée Vargas, Jyh-Ming Lien

  We propose to use an interactive 3D visualization tool, VIZMO++, which allows users to easily add nodes to a roadmap in difficult regions visually detected by the user. These nodes can be used as seed configurations that automatic planners can use to add more nodes around, to facilitate connection of existing roadmap components, or to identify areas to explore. The following pictures show the serial environment where a two-linked robot, has to pass through the narrow passages to get to its final configuration. We initially sampled 1000 CSpaceOBPRM nodes.

  The user visually detected the areas that could not be connected (the narrow passages) and added more nodes to try to make connections that could not be made before.

  Next, OBRRT was used to expand the user provided samples and then additional connections were attempted.

• Haptic

  ---

  Enhancing Randomized Motion Planners with Haptic Hints
  supported by NSF, Texas Higher Education Coordinating Board
  Nancy Amato
  Project Alumni: O. Burchan Bayazit, Guang Song
  

  We have studied problems involving rigid bodies moving among static obstacles, such as parts in mechanical assemblies, and ligand binding which is of interest in drug design. Our studies use the PHANToM haptic device by SensAble Technologies, Inc..

  We developed a simple roadmap visualization technique so that the human operator can see the the weakness of the roadmap generated by the automated planner. Later, the operator can use a haptic interface to improve this roadmap. The roadmap configurations are represented as scaled version of the robot in order be able to show not only translation but also orientation. These configurations can be either represented as wired robots or transparent robots. The connections between these configurations, i.e., the roadmap configuration then can be represented as lines. Different components of the roadmap would have different colors to classify them correctly. The figure in the left has one tube as the obstacle (the larger one) and another tube as the robot.

  After observing the roadmap, the user may improve the roadmap by generating either a configuration which the automated planner failed to find or a path to connect a disconnected part. Although there are numerous input methods (like keyboard, mouse, space-ball etc.) the best results can be achieved by using a haptic interface since the user would have a feeling of the environment. In order to simplify the user's task it is also possible to relax some constraints in the environment. The easiest way is to let the user be able to collect some collided path instead of collision free path. We called this path as approximate path . Later some algorithms may have been used to transform this approximate path to some collision free paths. The following figures show such an example. The robot in this example is the elbow shaped object. The goal is to move the robot inside the hole. The user had collected an approximate path to help the planner, later the planner used transformed this path to a collision free path. The configuration in the left is user generated. The configuration in the right is the same configuration pushed to free space. You can watch user generated path and computer enhanced path from our experiments.

  Approximate Path (avi)	Pushed Path (avi)

  In this work we also investigated an Iterative Pushing method, i.e., we solved an easier problem. Then we used the path generated for the easy version as an approximate path for harder problem. We repeated these steps until we reached the original problem.
  
  One of the challenges in haptic research is the very fast (i.e., ~1kHz) update requirements for force feedback. This limits the possible applications to very simple environments. However, we used a heuristic algorithm to approximate the force feedback, hence, achieved a realistic feedback even in the complex environments.
  
  

Using Motion Planning to Study Ligand Binding and Protein Folding, Nancy M. Amato, O. Burchan Bayazit, and Guang Song, Joint AI & Robotics Seminar and TAMBUG Meeting (Texas A&M Bioinformatics User Group), Texas A&M University, October 20, 2000.
TAMBUG Presentation ( html, ppt , compressed ppt )

Providing Haptic 'Hints' to Automatic Motion Planners, Burchan Bayazit, AI & Robotics Seminars , Department of Computer Science, Texas A&M University, Fall 1999.
Power-Point Presentation (Companion movies Approximate, Pushed , Final )

Related Projects

Ligand binding
Vizmo++

Papers

Vizmo

VIZMO++: a Visualization, Authoring, and Educational Tool for Motion Planning, Aimée Vargas E., Jyh-Ming Lien, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 727-732, Orlando, Florida, To appear, May 2006. Also, Technical Report, TR05-014, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Visualization Tools for Moving Objects, Aimée Vargas E., Masters Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, Dec 2005.
Masters Thesis(ps, pdf, abstract)

User-Guided Path Planning, Aimée Vargas, Jyh-Ming Lien, Marco A. Morales A., Samuel Rodriguez, Nancy M. Amato, Technical Report, TR05-011, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005.
Technical Report(ps, pdf, abstract)

Haptic

Enhancing Randomized Motion Planners: Exploring with Haptic Hints, O. Burchan Bayazit, Guang Song, Nancy M. Amato, Autonomous Robots, 10(2):163-174, 2001. Also, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 529-536, Apr 2000. Also, Technical Report, TR99-021, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 1999.
Proceedings(pdf, abstract)

Ligand Binding with OBPRM and Haptic User Input, O. Burchan Bayazit, Guang Song, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 954-959, May 2001.
Proceedings(ps, pdf, abstract)

Interactive Dynamic Simulation using Haptic Interaction, Wookho Son, Kyunghwan Kim, Nancy M. Amato, Jeffrey C. Trinkle, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 145-150, Nov 2000.
Proceedings(ps, pdf, abstract)

Ligand Binding with OBPRM and Haptic User Input: Enhancing Automatic Motion Planning with Virtual Touch, O. Burchan Bayazit, Guang Song, Nancy M. Amato, Technical Report, TR00-025, Department of Computer Science, Texas A&M University, Oct 2000.
Technical Report(ps, pdf, abstract)

Providing Haptic 'Hints' to Automatic Motion Planners, O. Burchan Bayazit, Guang Song, Nancy M. Amato, In Phantom Users Group Work. (PUG), Oct 1999.
Proceedings(ps, pdf, abstract)

Providing Haptic 'Hints' to Automatic Motion Planners, Nancy M. Amato, O. Burchan Bayazit, Kyunghwan Kim, Wookho Son, Guang Song, Technical Report, TR98-026, Department of Computer Science, Texas A&M University, Nov 1998.

Parasol Home | Research | People | General info | Seminars | Resources   Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  Contact Webmaster      Phone 979.458.0722     Fax 979.458.0718  Department of Computer Science | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science Engineering TAMU