Abstract
Multi-objective motion planning is a critical challenge in robotics, where agents must navigate environments while balancing conflicting goals such as path length, energy consumption, and safety. This paper introduces MORRF (Multi-Objective Rapidly exploring Random Forest), a sampling-based algorithm that efficiently finds a diverse set of Pareto optimal paths. By decomposing the multi-objective problem into scalar subproblems and utilizing a forest of trees that share vertices, MORRF* achieves superior convergence speed and solution quality compared to state-of-the-art evolutionary algorithms.
Introduction
In real-world robotics, "optimality" is rarely defined by a single metric. For instance, a drone mission might require minimizing flight time while maximizing signal strength and staying below a certain altitude. These objectives are often in direct conflict. The conventional approach of using a weighted sum to combine these objectives into a single scalar value has significant drawbacks: it requires human intuition to set weights and cannot find solutions in non-convex regions of the Pareto front.
While multi-objective evolutionary algorithms (MOEAs) like NSGA-II exist, they struggle with the high-dimensional, continuous nature of path planning. MORRF addresses these issues by extending the RRT framework into a multi-tree architecture designed for decomposition-based optimization.
Methodology
MORRF builds upon the Optimal Rapidly-exploring Random Tree (RRT) algorithm. Instead of a single tree, it maintains a "forest" of trees that share the same set of sampled vertices in the configuration space but maintain independent edge sets to optimize different criteria.
The architecture consists of two primary components:
- Reference Trees: $K$ trees are maintained, each optimizing one of the $K$ individual objectives. These trees help dynamically estimate the "Utopia vector"—the theoretical point where all objectives are minimized simultaneously.
- Subproblem Trees: $M$ trees are assigned to specific scalar subproblems. MORRF* uses the Tchebycheff decomposition method to divide the multi-objective space into these subproblems, each exploring a different trade-off region.
The key innovation lies in the shared vertex set. By sampling the environment once and allowing multiple "expert" trees to rewire edges according to their specific goals, the algorithm gains significant computational efficiency. As the reference trees improve their estimates of the Utopia vector, the subproblem trees become increasingly accurate in mapping the Pareto front.
Experimental Evaluation
The algorithm was tested in several simulated environments, including 2D obstacle-free spaces, 2D spaces with rectangular obstacles, and complex 3D objective spaces involving Euclidean distance and additional cost functions. These tests were designed to evaluate convergence speed, solution diversity, and the ability to handle search space discontinuities.
Key Results
MORRF* demonstrated significant improvements over traditional methods:
- Convergence Speed: In 2D simulations, MORRF converged much faster than NSGA-II. While NSGA-II produced sparse and unsatisfactory samples after 5,000 iterations, MORRF successfully mapped a clean, dense Pareto front.
- Solution Diversity: The use of Tchebycheff decomposition allowed for a more uniform distribution of solutions across the Pareto front compared to weighted-sum approaches, which often cluster solutions in specific regions.
- Robustness: The algorithm effectively handled obstacles, providing multiple path options that represented distinct cost trade-offs.
Conclusion and Future Work
MORRF* provides a robust and efficient framework for multi-objective path planning in continuous spaces. By combining sampling-based planning with decomposition-based optimization, it offers asymptotic optimality and high-quality solution sets. Future research will focus on reducing computational overhead, exploring non-uniform sampling techniques, and incorporating Bellman’s principle of optimality to ensure convergence to the Pareto set from any point within the tree structure.
Summary updated