Direction Informed Trees (DIT*): Optimal Path Planning via Direction Filter and Direction Cost Heuristic

Liding Zhang, Kejia Chen, Kuanqi Cai, Yu Zhang, Yixuan Dang, Yansong Wu, Zhenshan Bing, Fan Wu, Sami Haddadin, Alois Knoll

Introduction

Motion planning in high-dimensional configuration spaces (C-spaces) remains a significant challenge in robotics due to the "curse of dimensionality." While sampling-based planners like RRT and BIT provide asymptotic optimality, their convergence speed is often hindered by inefficient exploration. State-of-the-art (SOTA) planners like Effort Informed Trees (EIT*) utilize heuristics to estimate cost-to-go, yet they frequently lack a mechanism to prioritize the most promising search directions. This often results in redundant collision checking—the primary computational bottleneck in path planning.

Direction Informed Trees (DIT) addresses this by explicitly optimizing the search direction. By integrating a directional filter and a novel direction-based cost heuristic, DIT accelerates the discovery of initial solutions while maintaining the theoretical guarantees of probabilistic completeness and asymptotic optimality.

Methodology: Directional Intelligence

DIT* introduces "directional intelligence" into the bidirectional search process through several key innovations:

1. Direction Filter

To minimize expensive collision checks, DIT* employs a directional filter. This filter evaluates potential neighbors by calculating the weighted cosine similarity between the current search direction and the goal direction. Neighbors that do not align with a favorable "area to explore" are pruned before validation, significantly reducing the search space.

2. Direction Cost Heuristic ($\bar{dc}$)

The algorithm introduces an inadmissible heuristic inspired by sigmoid functions. This heuristic quantifies the deviation of a potential edge from the ideal goal direction. While inadmissible heuristics do not guarantee optimality on their own, they are highly effective at guiding the search toward a "good enough" initial solution quickly.

3. Lexicographical Ordering

DIT* prioritizes its search queue using a hierarchical approach. It first considers the projected lower bound of the total cost (admissible), followed by estimated effort, and finally the minimal directional cost. This ensures that among paths with similar estimated costs, the one pointing most directly toward the goal is explored first.

Evaluation and Real-World Application

The performance of DIT* was benchmarked using the Open Motion Planning Library (OMPL) across various simulated environments, including "Random Rectangles" and "Narrow Passages" in dimensions ranging from $\mathbb{R}^4$ to $\mathbb{R}^{16}$.

Beyond simulations, the planner was validated on complex real-world robotic tasks involving high degrees of freedom:

  • 7-DoF Single-Arm Manipulator: Reaching into drawers in a kitchen environment.
  • 14-DoF Dual-Arm Manipulator: A complex cable routing task requiring the robot to clip a flexible cable into specific fixtures.
Components of the dual-arm cable routing task: the flexible cable and the clip fixture.

In the dual-arm task, DIT* demonstrated more goal-oriented behavior compared to standard RRT-based methods, which often exhibit aimless exploration in high-dimensional spaces.

A 14-DoF dual-arm manipulator utilizing DIT* to perform a complex cable routing and fixture clipping task.

Key Results

DIT* consistently outperforms SOTA planners, particularly as dimensionality increases:

  • Faster Initial Solutions: In $\mathbb{R}^{16}$ narrow passage scenarios, DIT reduced the median time to find an initial solution ($t_{init}$) by 45.08% compared to EIT.
  • Improved Path Quality: Initial paths found by DIT were significantly shorter. For example, in $\mathbb{R}^8$ environments, initial path lengths were 23.68% shorter than those produced by EIT.
  • Scalability: The performance advantage of DIT* grows with the dimensionality of the problem, making it a robust choice for complex multi-DoF systems.

Conclusion

Direction Informed Trees (DIT*) represents a significant advancement in sampling-based motion planning. By treating search as a directional process rather than just a distance-minimization problem, it achieves substantially faster convergence. Future work will explore extending these directional heuristics to dynamic environments and incorporating kinodynamic constraints to handle robot velocity and acceleration limits.

Summary updated

BibTeX
@inproceedings{zhang2025direction,
  author = {Liding Zhang and Kejia Chen and Kuanqi Cai and Yu Zhang and Yixuan Dang and Yansong Wu and Zhenshan Bing and Fan Wu and Sami Haddadin and Alois Knoll},
  title = {{Direction Informed Trees (DIT*): Optimal Path Planning via Direction Filter and Direction Cost Heuristic}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2025},
  doi = {10.1109/icra55743.2025.11127725},
}
Figure