A Pareto Optimal D* Search Algorithm for Multiobjective Path Planning
  Path planning is one of the most vital elements of mobile robotics, providing
the agent with a collision-free route through the workspace. The global path
plan can be calculated with a variety of informed search algorithms, most
notably the A* search method, guaranteed to deliver a complete and optimal
solution that minimizes the path cost. D* is widely used for its dynamic
replanning capabilities. Path planning optimization typically looks to minimize
the distance traversed from start to goal, but many mobile robot applications
call for additional path planning objectives, presenting a multiobjective
optimization (MOO) problem. Common search algorithms, e.g. A* and D*, are not
well suited for MOO problems, yielding suboptimal results. The search algorithm
presented in this paper is designed for optimal MOO path planning. The
algorithm incorporates Pareto optimality into D*, and is thus named D*-PO.
Non-dominated solution paths are guaranteed by calculating the Pareto front at
each search step. Simulations were run to model a planetary exploration rover
in a Mars environment, with five path costs. The results show the new, Pareto
optimal D*-PO outperforms the traditional A* and D* algorithms for MOO path
planning.
