Amity School of Engineering & Technology

Session 2:
Metric Path Planning

By
Dr. Ashok Kumar
 Amity School of Engineering & Technology

Introduction to Metric Path Planning

•Definition: Planning a robot's path in continuous, metric spaces.
•Focuses on precise geometrical and mathematical computations.
•Importance in robotics for tasks requiring accuracy and efficiency.

Objectives of Metric Path Planning

•Primary Goals:
• Find a collision-free path.
• Optimize path length, energy, or time.
•Applications:
• Autonomous vehicles, warehouse robots, robotic surgery.
 Amity School of Engineering & Technology

Key Characteristics
•Continuous Space: Requires handling of real-world, non-discrete
environments.
•Metric Representation: Utilizes Cartesian or other coordinate systems.
•Complexity: Accounts for obstacles, dynamic environments, and robot
constraints

Types of Metric Path Planning Methods

[Link] Methods:
1. Exact solutions, e.g., cell decomposition and visibility graphs.
[Link]-Based Methods:
1. Approximate solutions, e.g., Probabilistic Roadmaps (PRMs) and
Rapidly-exploring Random Trees (RRTs).
 Amity School of Engineering & Technology

Deterministic Metric Planning

•Cell Decomposition:
• Divides space into manageable cells.
• Example: Trapezoidal or grid-based decomposition.

Sampling-Based Metric Planning

•Probabilistic Roadmaps (PRMs):
• Randomly samples points in the environment and connects them to
form a graph.
• Efficient for high-dimensional spaces.
•Rapidly-exploring Random Trees (RRTs):
• Grows a tree from the start to the goal.
• Effective for large and complex environments.
 Amity School of Engineering & Technology

Path Planning Algorithms in Metric Spaces

[Link]’s Algorithm:
1. Finds the shortest path in weighted graphs.
2.A Algorithm:*
1. Combines shortest path optimization with heuristics.

Metrics in Path Optimization

•Distance: Shortest geometric path.
•Energy Consumption: Optimal for robotic energy efficiency.
•Time: Minimizes traversal time.
•Smoothness: Avoids abrupt changes in direction.
 Amity School of Engineering & Technology

Introduction to Cell Decomposition

•Definition: A method to solve path planning problems by dividing the
environment into simple, manageable regions (cells).
•Purpose: To simplify pathfinding in complex environments.
•Key Focus: Ensuring the robot finds a collision-free path.

Types of Cell Decomposition

[Link] Cell Decomposition:
1. Divides the space into non-overlapping cells that exactly cover free
space.
2. Examples: Trapezoidal Decomposition.
[Link] Cell Decomposition:
1. Uses a grid-like structure for approximation.
2. Examples: Quadtrees, Octrees.
 Amity School of Engineering & Technology

Exact Cell Decomposition

•Definition:
• Ensures complete and accurate representation of free space.
•Methods:
• Trapezoidal Decomposition: Divides space into trapezoids using
obstacle edges.
• Visibility Graphs: Links visible points to create a graph for navigation.
•Advantages: Accurate and guarantees pathfinding.
•Limitations: Computationally expensive.
 Amity School of Engineering & Technology

Approximate Cell Decomposition

•Definition:
• Represents space as a grid of cells where each cell is marked as free
or occupied.
•Methods:
• Quadtrees: Hierarchical division of space into four quadrants.
• Octrees: Extends quadtree concept to 3D.
•Advantages: Simpler implementation and scalable to large spaces.
•Limitations: Precision depends on grid resolution.
 Amity School of Engineering & Technology

Comparison of Exact and Approximate Methods

 Amity School of Engineering & Technology

Steps in Cell Decomposition

[Link] Representation:
1. Identify boundaries and obstacles.
[Link] Division:
1. Divide the space into free and obstacle regions.
[Link] Creation:
1. Create adjacency relationships between free cells.
[Link]:
1. Apply algorithms (e.g., Dijkstra’s or A*) on the cell graph.
 Amity School of Engineering & Technology

Advantages of Cell Decomposition

•Simplifies pathfinding by reducing complexity.
•Applicable to both 2D and 3D environments.
•Flexible: Can integrate with other planning methods.

Challenges in Cell Decomposition

•Exact methods are computationally intensive.
•Approximate methods may miss narrow passages.
•Memory usage increases with higher resolution.
•Requires preprocessing for dynamic environments.
 Amity School of Engineering & Technology

Introduction to Probabilistic Roadmaps (PRMs)

•Definition: A sampling-based motion planning algorithm that constructs a
graph in the configuration space of a robot.
•Key Features:
• Works well in high-dimensional spaces.
• Uses random sampling to handle complex environments.

Key Components of PRMs

[Link] Space (C-Space): Represents all possible positions of the
robot.
[Link]: Randomly generates nodes in the free space.
[Link] Construction: Connects nearby nodes to form a graph.
[Link] Query: Uses the roadmap to find a path from the start to the goal.
 Amity School of Engineering & Technology

Algorithm for Probabilistic Roadmaps

[Link] Phase:
1. Generate random samples in free space.
2. Connect samples to their nearest neighbors if the path is collision-free.
[Link] Phase:
1. Add the start and goal nodes to the graph.
2. Find the shortest path using a graph search algorithm (e.g., Dijkstra’s).
 Amity School of Engineering & Technology

Steps in PRM Construction

[Link]:
1. Uniform random sampling or bias towards difficult regions.
[Link] Checking:
1. Ensure samples and edges are in free space.
[Link] Formation:
1. Connect nodes based on proximity (k-nearest neighbors or fixed-
radius).
[Link]:
1. Search for the optimal path on the graph.
 Amity School of Engineering & Technology

Advantages of PRMs
•Efficient for high-dimensional and complex spaces.
•Applicable to multiple queries once the roadmap is built.
•Handles both static and quasi-dynamic environments.

Limitations of PRMs
•Quality of paths depends on the number and distribution of
samples.
•Computational overhead in collision checking for dense
environments.
•Requires precomputation and is less suitable for fully dynamic
settings.
 Amity School of Engineering & Technology

Introduction to RRTs
•Definition: RRT is a tree-based path planning algorithm that incrementally
builds a tree by randomly sampling the space and extending towards the
goal.
•Key Features:
• Sampling-based, asymptotically optimal.
• Focuses on high-dimensional spaces and complex environments.
Key Concepts of RRTs
•Configuration Space (C-Space): The space where each point
corresponds to a possible configuration of the robot.
•Tree Growth: Tree starts at an initial configuration and grows by
sampling random points in the C-space and connecting them to the
nearest node in the tree.
 Amity School of Engineering & Technology

RRT Algorithm Overview

[Link]:
1. Start with an initial configuration and build an empty tree.
[Link]:
1. Sample random points in the C-space.
[Link] Extension:
1. Find the nearest node in the tree and extend the tree toward the
random sample.
[Link]:
1. Repeat the sampling and extension until a path is found or a maximum
number of iterations is reached.
 Amity School of Engineering & Technology

RRT Algorithm Step-by-Step

[Link] Node:
1. Initialize the tree with the starting configuration of the robot.
[Link] Sample Generation:
1. Generate random samples in the C-space.
[Link] Nearest Node:
1. Identify the nearest node in the tree to the random sample.
[Link] Tree:
1. Move the tree from the nearest node toward the random sample by a
small step.
[Link] Check:
1. Ensure the new node does not collide with obstacles.
[Link]:
1. Stop when the goal is reached or a maximum number of iterations is
exceeded.
 Amity School of Engineering & Technology

Advantages of RRTs
•Scalability:
• Works well in high-dimensional spaces and complex environments.
•Simplicity:
• Easy to implement with basic operations.
•Versatility:
• Can be adapted for different types of robots and environments.

Limitations of RRTs
•Path Quality:
• The initial path may not be optimal and may require post-processing.
•Computational Complexity:
• Can be slow for very high-dimensional or cluttered spaces.
•Dependency on Sampling:
• The efficiency depends on how well the space is sampled
 Amity School of Engineering & Technology

Challenges in Metric Path Planning

•Complex environments with irregular shapes and moving obstacles.
•Computational load for large-scale and high-dimensional problems.
•Handling uncertainties in robot and environment modeling.

Applications of Metric Path Planning

[Link] Vehicles: Navigation in traffic.
[Link] Automation: Path planning for robotic arms.
[Link]: Robotic surgeries requiring precision.
[Link]: Navigation of drones in 3D spaces.
 Amity School of Engineering & Technology

Comparison of Metric Path Planning Techniques