# Long-Range Navigation in Complex and Dynamic Environments with Full-Stack S-DOVS +
## 2 Background
### Related Work  
The complexity of autonomous navigation increases when the environment changes. Conventional global planning algorithms such as RRT [3] or A\({}^{*}\)[4] and their subsequent improvements [5; 6] compute a plan that the robot should follow regarding the map information. Then, a local planner uses the information from the robot's sensors to consider the changes in the environment and follow the global plan. An example of a local planner is the Dynamic Window Approach (DWA) [7], which iteratively computes the velocity of the robot considering its kinodynamic constraints, the sensed distance to obstacles, and the position of the goal. This approach was extended in [8] to consider high-velocity motion. The problem with the DWA is that it does not consider the velocity and trajectories of the obstacles, only taking into account their current position. Alternative methods to control the movement of the robot have been proposed. For instance, the robot's movement can be represented as the outcome of potential forces, such as the artificial potential fields proposed in [9]. Other methods model the environment as a spring-mass system (i.e., an elastic band), as in [10]. Dynamic environments pose a significant challenge for navigation planning, as they require real-time adaptation to constantly changing surroundings. Planners have been developed to address this issue, such as those presented in [11; 12; 13]. Several of the previously mentioned approaches for navigating in static environments have been extended to adapt to changing environments. The DWA can be improved by predicting the future trajectories of obstacles using holonomic controllers [14] or by adapting the DWA parameters for each situation using a deep neural network [15]. The Time Elastic Band (TEB) approach [16] proposed modeling the changes in the environment over time as elastic bands. Including dynamic obstacles in the model requires a more complex representation than simply using their positions, as in the static case. A wide range of methods use the velocity of the obstacles in the model to achieve better performance. Two models that have been widely used in the literature are the inevitable collision states (ICS) and the Velocity Obstacle (VO). ICS, introduced in [17], uses the dynamics of the system and the obstacles to compute future states where a collision is inevitable. This model considers the time it would take for the robot to stop or avoid the obstacle, which can be essential in fast-changing environments. On the other hand, VO, introduced in [18], is defined by the trajectories that the dynamic obstacles have in time. It computes those velocities that could cause a collision with the robot, after which the velocities that are not inside the velocity obstacles are available to be chosen by the robot. The VO model ensures that the robot dynamics are respected, making it a suitable choice for scenarios with complex obstacle dynamics. The VO was extended in [1] with Dynamic Object Velocity Space (DOVS), representing the dynamism and future of the environment. A local planner called S-DOVS that includes the robot's kinodynamic constraints was developed. The S-DOVS strategy-based planner identifies various situations based on the relative variables between the robot and moving objects, then applies a different action for each situation in order to balance the time to goal and robot safety. In recent years, motion planning in dynamic environments has been tackled by learning approaches such as reinforcement learning, as demonstrated in various works, including [19; 20; 21], as well as by [22; 23], which also incorporated the DOVS model. However, these methods face limitations due to the complexity of the real world and the large number of variables involved. Although they attempt to address the limitations of model-based approaches, there remains a large gap between the simulators used for training and real-world scenarios.