MOD* Lite: An Incremental Path Planning Algorithm Taking Care of Multiple Objectives

Abstract

The need for determining a path from an initial location to a target one is a crucial task in many applications, such as virtual simulations, robotics, and computer games. Almost all of the existing algorithms are designed to find optimal or suboptimal solutions considering only a single objective, namely path length. However, in many real life application path length is not the sole criteria for optimization, there are more than one criteria to be optimized that cannot be transformed to each other. In this paper, we introduce a novel multiobjective incremental algorithm, multiobjective D* lite (MOD* lite) built upon a well-known path planning algorithm, D* lite. A number of experiments are designed to compare the solution quality and execution time requirements of MOD* lite with the multiobjective A* algorithm, an alternative genetic algorithm we developed multiobjective genetic path planning and the strength Pareto evolutionary algorithm.