Path Planning in Dynamic Environments

The motion planning problem for mobile robots is typically formulated as follows: given a robot and a description of an environ- ment, plan a path of the robot between two specified locations, which is collision-free and satisfies certain optimization criteria. Traditionally there are two approaches to the problem: O-line planning, which as- sumes perfectly known and stable environment, and on-line planning, which focuses on dealing with uncertainties when the robot traverses the environment. On-line planning is also referred to by many researchers as the navigation problem. Additional diculties in approaching nav- igation problem is that some environments are dynamic, i.e., the ob- stacles which are present there, need not be static. In this paper we consider a particular instance of a navigation problem, namely, a prob- lem of computing a near-optimum trajectory of a ship. By taking into account certain boundaries of the maneuvering region, along with nav- igation obstacles and other moving ships, the problem of avoiding col- lisions at sea was reduced to a dynamic optimization task with static and dynamic constrains. The paper presents a modified version of the Evolutionary Planner/Navigator algorithm, #EP/N++, to address the problem. The introduction of a time parameter, the variable speed of the ship, and time-varying constraints representing movable ships, are the main features of the new system. Sample results, having the form of ship trajectories obtained using the program for navigation situations are also presented.