Bolded items represent paper sections and heading, grey items are things we are not sure of. Blue → Protein, Purple → Robotics

• Outline Resources

1. Introduction

   • Motion planning refers to the process of finding an obstacle-free path for robots, given a starting point and a goal destination.
   • Applications of motion planning are wide ranging.
     • Basic examples of how any problem with a "robot" and a target can be formulated as a motion planning problem.
   • It is computationally hard to plan for robot navigation because of how difficult it is to capture all the robot constraints and represent the environment as a simple model to a computer.
   • Problem Statement:
     • Existing motion planning methods uses workspace property to guide planning process.
   • Motivation:
     • Skeleton-guided planner are the state-of-the art methods that uses workspace property to guide planning. Although there are effective, we can utilize more features of the workspace to help us plan faster
       • Although current state of the art Motion Planning algorithms uses the workspace property to guide planning, they are not using these features to further improve planning
       • These methods are
       • Example: biasing for safety → clearance (robotics), and energy (protein)
   • Our Contribution:
     • We introduce the idea of using metrics for biasing workspace exploration
     • Clearance
     • Robotics → Clearance
       • We apply the clearance metric on robotics applications.
       • In Robotics, we use clearance to find safer and shorter paths while also solving the bottlenecks of sampling based planning.
     • Protein-ligand → Energy
       • We can extend to the Protein-Ligand binding problem, applying both the clearance method as well as an additional energy metric for biasing.
       • We want to understand and evaluate the tunnels of the protein that the ligand would most likely be able to access in order to reach the binding site.
       • In order to gain insight on meaningful tunnels, we want to find tunnels of high volume and low energy.
     • Protein-Ligand → Energy & Clearance?
   • Our experiments shows that using our metrics we are able to generate safer paths faster for both the robotics and protein application of motion planning.

2. Related Work

   1. The Motion Planning Problem
      • Motion Planning is a geometry problem.
        • In depth explanation of motion planning as a geometry problem (C-space, Free-space, configuration, etc.)
      • The motion planning problem can be extended to applications outside robotics.
        • One paragraph that lists the application and cites them. And also introduces the Protein-Ligand application.
      1. Protein-Ligand Binding Problem
         • A protein is a structure made up of a chain of amino acids.
         • There exists regions on the protein where a certain small drug molecule, called a Ligand, can interact and bind to.
   2. Sampling Based Planning
      • Sampling-based planning is the current state-of the art approach to the motion planning problem.
      1. Rapidly-exploring Random Trees (RRTs)
         • An RRT is a sampling-based planner that grows a tree for solving the motion planning problem.
         • RRTs are able to explore the workspace and are good for solving single query problems.
      2. Probabilistic Roadmap (PRM)
         • PRM takes a graph based approach to solving the motion planning problem
         • Advantages of PRM
   3. Guided Motion Planning
      1. Topological Guidance
         • Topological guidance involves using the workspace structure to direct how sampling based planners like PRM and RRT explores the environment.
         • Workspace Skeletons is an example of topological guidance. They are graphs which captures the topological features of the environment.
         • For our experiment we use the Mean Curvature Skeleton (MCS) to guide environment exploration.
      2. Planning
         • We use different planners based on the motion planning problem.
         • Dynamic Region Rapidly-exploring Random Tree (DR-RRT) is a skeleton-guided RRT which uses the workspace skeleton to bias RRT growth.
           • DR-RRT is faster and returns lower collision detection calls when compared to basic RRT
         • Dynamic Region Rapidly-exploring Random Graph (DR-RRG) is a skeleton-guided strategy that combines PRM and RRT.

3. Method

   1. Algorithm

      1. Pseudocode

         

         Initial Pseudocode for the paper and Regina's Poster. Reviewed and confirmed by Diane

      • Algorithm explanation with Figures

        

        Figure (a): env with start and goal

        

        Figure (b): env with skeleton

        

        Figure (c): Annotated skeleton

        

        Figure (d): Roadmap

        • Our method is designed for skeleton-guided RRTs and applied to DR-RRT or and DR-RRG depending on the problem.
        • Using the example in figure(a), our method takes as input ....
        • Clearance Annotated Skeleton colors the highest clearance regions starting with red, and then to yellow with the lowest clearance being green and then blue.
        • Intervals are calculated by taking the maximum clearance and minimum clearance and dividing into equal parts. In this case, there are four intervals, but a more detailed skeleton can be generated.

   2. Metrics

      1. Computing Clearance-value
         • Clearance-value is defined as the size of free space between obstacles in the environment
      2. Computing Energy-value
         • Our energy function calculates the energy of each region based on Van der waals interactions, which are weak intermolecular forces between two atoms or molecules.

4. Experiments

   • We tested our method in robotics and protein environments.
   • We tested our method in robotics and protein environments. For each experiment, we averaged the following data over ten random seeds.
   • Experimental Setup
   1. Robotics Experiments:
      • Environment Setup
      • Results
      • Discussion
   2. Protein Experiments:
      1. Experiment Set-up
         • Environment: fbw protein
         • We can compare energy biasing, clearance biasing and no-biasing (using topology).
      2. Results
      • Table
      1. Discussion
         • Our method finds the most energetically favorable tunnels faster when looking at complex protein environments

5. Conclusions

   • We can exploit workspace properties such as energy and clearance to find more feasible paths in faster time.
   1. Future Work
      • Theory
        • Metrics can be designed for any motion planning problem that would benefit from biasing exploration exploration based on properties particular to the problem or its application.
      • Robotics
        • Compare our method to current methods in Image-guided Medical Needle Steering by running 3D experiments. The medical robotics application
        • Run our method is animation environments and compare with current methods for planning animation movements
      • Protein
        • We can explore the problem of dynamically changing proteins by adding a new bio-metric of flexibility to our biasing strategy

6. Acknowledgments

   • CRA-W DREU
   • University of Illinois at Urbana Champaign

7. References