Bolded items represent paper sections and heading, grey items are things we are not sure of. Blue → Protein, Purple → Robotics
- 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.
- 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
- 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.
- 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.
- 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.
- Sampling Based Planning
- Sampling-based planning is the current state-of the art approach to the motion planning problem.
- 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.
- Probabilistic Roadmap (PRM)
- PRM takes a graph based approach to solving the motion planning problem
- Advantages of PRM
- Guided Motion Planning
- 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.
- 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.
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.
- Computing Clearance-value
- Clearance-value is defined as the size of free space between obstacles in the environment
- 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.
- 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
- Robotics Experiments:
- Environment Setup
- Protein Experiments:
- Experiment Set-up
- Environment: fbw protein
- We can compare energy biasing, clearance biasing and no-biasing (using topology).
- Our method finds the most energetically favorable tunnels faster when looking at complex protein environments
- We can exploit workspace properties such as energy and clearance to find more feasible paths in faster time.
- Future Work
- 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.
- 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
- We can explore the problem of dynamically changing proteins by adding a new bio-metric of flexibility to our biasing strategy
- CRA-W DREU
- University of Illinois at Urbana Champaign