Glossary

8.2 Path planning and obstacle avoidance algorithms

9 min read•july 30, 2024

Path planning and obstacle avoidance are crucial for autonomous underwater vehicles (AUVs). These algorithms help AUVs navigate safely and efficiently in complex underwater environments. From global to local planning, various techniques like Dijkstra's, A*, RRT, and PRM are used to find optimal routes.

Grid-based and sampling-based methods offer different approaches to path planning. Obstacle avoidance algorithms, both reactive and deliberative, work alongside path planning to ensure safe navigation. Evaluating these algorithms involves considering efficiency metrics and to uncertainties in the underwater environment.

Path planning algorithms for AUVs

Classifications and characteristics of path planning algorithms

Top images from around the web for Classifications and characteristics of path planning algorithms

  • Frontiers | Path Following, Obstacle Detection and Obstacle Avoidance for Thrusted Underwater ... View original

    Is this image relevant?

  • Rapid global path planning algorithm for unmanned surface vehicles in large-scale and multi ... View original

    Is this image relevant?

  • Frontiers | Path Following, Obstacle Detection and Obstacle Avoidance for Thrusted Underwater ... View original

    Is this image relevant?

1 of 3

Top images from around the web for Classifications and characteristics of path planning algorithms

  • Frontiers | Path Following, Obstacle Detection and Obstacle Avoidance for Thrusted Underwater ... View original

    Is this image relevant?

  • Rapid global path planning algorithm for unmanned surface vehicles in large-scale and multi ... View original

    Is this image relevant?

  • Frontiers | Path Following, Obstacle Detection and Obstacle Avoidance for Thrusted Underwater ... View original

    Is this image relevant?

1 of 3
  • Path planning is the process of finding a feasible and optimal route for an autonomous vehicle to navigate from a start position to a goal position while avoiding obstacles in the environment
  • Path planning algorithms can be classified into two main categories: and
    • Global path planning generates a complete path from the start to the goal based on a priori knowledge of the environment, such as a map or a grid representation
    • Local path planning generates a partial path based on the immediate surroundings of the vehicle, using real-time sensor data to avoid obstacles and adjust the path dynamically
  • Path planning algorithms need to consider the kinematic and dynamic constraints of the AUV, such as its turning radius, maximum velocity, and acceleration limits, to generate feasible paths

Common path planning algorithms for underwater navigation

  • : A graph-based algorithm that finds the shortest path between nodes in a graph by iteratively expanding the path with the lowest cost
    • Dijkstra's algorithm guarantees the optimal path but can be computationally expensive for large graphs
    • It can be used for global path planning when the environment is known and represented as a graph
  • : An extension of Dijkstra's algorithm that uses heuristics to guide the search towards the goal, reducing the number of nodes explored
    • A* algorithm combines the actual cost from the start node with an estimated cost to the goal node, using heuristics such as the Euclidean distance
    • It is more efficient than Dijkstra's algorithm for large environments and can be used for both global and local path planning
  • : A sampling-based algorithm that incrementally builds a tree of feasible paths by randomly sampling points in the configuration space and connecting them to the nearest node in the tree
    • RRT can handle high-dimensional configuration spaces and complex environments with obstacles
    • It is probabilistically complete, meaning that it will find a feasible path if one exists, given enough time
  • : Another sampling-based algorithm that constructs a graph of feasible paths by randomly sampling points in the configuration space and connecting them with collision-free edges
    • PRM is suitable for multi-query path planning, where multiple paths need to be generated in the same environment
    • It can be combined with graph search algorithms, such as Dijkstra's or A*, to find the optimal path in the constructed roadmap

Grid-based vs sampling-based path planning

Grid-based path planning techniques

  • techniques discretize the environment into a grid of cells, where each cell represents a small portion of the environment
    • represent the environment as a binary grid, where each cell is either occupied (contains an obstacle) or free (navigable)
    • represent the environment as a grid of cells with varying heights, allowing for 3D path planning in underwater environments with varying depths
  • Grid-based path planning algorithms, such as A*, can be applied to the discretized environment to find the optimal path from the start cell to the goal cell
    • The cost function for grid-based path planning can include factors such as the distance traveled, the time taken, and the risk of collision with obstacles
    • Heuristics, such as the Euclidean distance or the Manhattan distance, can be used to estimate the cost from a given cell to the goal cell and guide the search
  • Grid-based techniques are simple to implement and can guarantee the optimal path, but they may suffer from the curse of dimensionality in high-dimensional configuration spaces

Sampling-based path planning techniques

  • techniques, such as RRT and PRM, explore the continuous configuration space of the AUV by randomly sampling points and connecting them with feasible paths
    • The configuration space represents all possible states of the AUV, including its position, orientation, and velocity
    • Sampling-based techniques can handle high-dimensional configuration spaces and complex environments more efficiently than grid-based techniques
  • RRT incrementally builds a tree of feasible paths by randomly sampling points and connecting them to the nearest node in the tree
    • The tree is expanded towards unexplored regions of the configuration space, allowing for efficient exploration
    • RRT can be extended to handle dynamic environments and moving obstacles, using variants such as RRT* and RRT-Connect
  • PRM constructs a graph of feasible paths by randomly sampling points and connecting them with collision-free edges
    • The graph can be preprocessed offline and used for multiple path queries in the same environment
    • PRM can be combined with graph search algorithms to find the optimal path in the constructed roadmap
  • Implementing path planning techniques for AUVs requires considering the specific characteristics of the underwater environment, such as the presence of , the limited communication range, and the uncertainty in sensor measurements

Obstacle avoidance in underwater navigation

Reactive and deliberative obstacle avoidance algorithms

  • Obstacle avoidance is the process of detecting and avoiding collisions with obstacles in the environment while navigating towards the goal
  • Obstacle avoidance algorithms can be classified into two main categories: reactive and deliberative
    • algorithms generate immediate control commands based on the current sensor readings, without maintaining a long-term plan. Examples include the and the
    • algorithms incorporate the obstacle information into the path planning process, generating a new path that avoids the detected obstacles. Examples include the and the elastic band approach
  • Reactive obstacle avoidance algorithms are computationally efficient and can handle , but they may suffer from local minima and oscillations in complex environments
  • Deliberative obstacle avoidance algorithms can generate globally optimal paths, but they require more computational resources and may not be suitable for real-time navigation in fast-changing environments

Integration of obstacle avoidance with path planning

  • Integrating obstacle avoidance with path planning involves continuously updating the planned path based on the newly detected obstacles and the changing environment
    • Local path planning techniques, such as the dynamic window approach, can be used to generate short-term paths that avoid obstacles while following the global path
    • The global path can be re-planned periodically or triggered by significant changes in the environment, such as the detection of a new obstacle or a change in the goal position
  • Hybrid approaches combining reactive and deliberative obstacle avoidance can be used to balance the trade-off between efficiency and optimality
    • For example, a reactive algorithm can be used for immediate obstacle avoidance, while a deliberative algorithm is used for long-term path planning and re-planning
    • The switching between the reactive and deliberative modes can be based on the urgency of the situation and the available computational resources
  • Obstacle avoidance algorithms for AUVs need to handle the uncertainty in underwater perception, such as the limited field of view of sonar sensors and the presence of noise and false positives in the sensor data
    • Sensor fusion techniques, such as or , can be used to combine data from multiple sensors and estimate the state of the environment more accurately
    • Probabilistic obstacle avoidance methods, such as the or the , can incorporate the uncertainty in the obstacle detection into the path planning process

Evaluating path planning efficiency and robustness

Metrics for evaluating path planning efficiency

  • The efficiency of a path planning algorithm can be measured by various metrics, such as:
    • : The total distance traveled by the AUV from the start to the goal position
      • Shorter paths are generally preferred to minimize energy consumption and time taken
      • However, the shortest path may not always be the most efficient path, considering other factors such as the risk of collision and the energy required for turning and accelerating
    • : The time taken by the algorithm to generate the path, which is critical for real-time navigation in dynamic environments
      • Faster computation times allow for more frequent re-planning and adaptation to changing environments
      • However, faster computation times may come at the cost of suboptimal paths or reduced robustness
    • : The amount of memory required by the algorithm to store the environment representation and the generated path
      • Lower memory usage is preferred for AUVs with limited onboard computational resources
      • However, lower memory usage may limit the complexity of the environment representation and the length of the generated path
  • The relative importance of these metrics depends on the specific application and the available resources of the AUV

Robustness evaluation and comparative analysis

  • The robustness of a path planning algorithm refers to its ability to handle uncertainties and changes in the environment, such as:
    • : The algorithm should be able to generate feasible paths even with noisy and incomplete sensor data
      • Robust algorithms should incorporate sensor uncertainty models and use probabilistic techniques to estimate the true state of the environment
      • Redundancy in sensing, such as using multiple sensors with different modalities, can improve the robustness to sensor failures and errors
    • Dynamic obstacles: The algorithm should be able to avoid moving obstacles and adapt the path in real-time
      • Robust algorithms should predict the future motion of the obstacles based on their current velocity and direction
      • Reactive obstacle avoidance techniques can be used to quickly respond to sudden changes in the obstacle motion
    • : The algorithm should be able to re-plan the path when the environment changes, such as when new obstacles are detected or when the goal position is updated
      • Robust algorithms should continuously monitor the environment and update the internal representation based on the new information
      • Incremental path planning techniques, such as and , can efficiently repair the existing path when the environment changes, instead of re-planning from scratch
  • Comparative analysis of different path planning and obstacle avoidance approaches can be performed through simulations and real-world experiments
    • Simulation environments, such as or , can be used to test and evaluate the algorithms in various scenarios with different environment configurations and obstacle types
      • Simulations allow for controlled and repeatable experiments, facilitating the comparison of different algorithms under the same conditions
      • However, simulations may not capture all the uncertainties and challenges of real-world environments, such as the effects of currents and the variability in sensor performance
    • Real-world experiments with physical AUVs can validate the simulation results and assess the practicality and reliability of the algorithms in actual underwater conditions
      • Real-world experiments provide the most realistic evaluation of the algorithms, considering the full range of environmental factors and the limitations of the AUV hardware and software
      • However, real-world experiments are more costly and time-consuming than simulations, and they may not be feasible for all scenarios and environments
  • The choice of the path planning and obstacle avoidance approach depends on the specific requirements and constraints of the application, such as the available computational resources, the sensor capabilities, and the mission objectives
    • For example, a mission requiring long-range navigation in a largely unknown environment may prioritize the robustness and adaptability of the algorithm over the optimality and efficiency of the generated path
    • On the other hand, a mission requiring precise and fast navigation in a well-known environment may prioritize the efficiency and computational speed of the algorithm over its robustness to environmental changes and uncertainties

Key Terms to Review (32)

A* algorithm: The A* algorithm is a popular pathfinding and graph traversal algorithm that is used to find the shortest path from a start node to a goal node. It combines features of Dijkstra's algorithm and greedy best-first search, using a heuristic to guide its search for efficiency. This makes it particularly effective in navigating complex environments with obstacles, where efficient real-time decision making and adaptive mission planning are essential.
Belief Roadmap Method: The belief roadmap method is a strategic approach used in robotics and artificial intelligence that maps out the beliefs or knowledge a robot has about its environment to effectively plan paths and avoid obstacles. This method combines the understanding of the robot's internal beliefs with external environmental factors, allowing it to make informed decisions while navigating complex spaces. By focusing on the robot’s understanding of its surroundings, this approach enhances obstacle avoidance and optimal path planning.
Computation time: Computation time refers to the duration required by an algorithm to process data and generate a result. In the context of path planning and obstacle avoidance algorithms, it is crucial as it directly impacts the efficiency and responsiveness of robotic systems when navigating through environments. The faster an algorithm can compute a path or avoid obstacles, the more effective the robotic system becomes in real-time scenarios.
Currents: Currents are continuous, directed movements of water generated by various forces, such as wind, the Earth's rotation, and differences in water temperature and salinity. These water flows can significantly affect the navigation, performance, and operational effectiveness of underwater vehicles and robotics, influencing their path planning, mission objectives, and adaptability to the marine environment's challenges.
D*: d* is a path planning algorithm that is an extension of Dijkstra's algorithm, designed for dynamic environments where obstacles may change during the execution of the path. It efficiently recalculates paths by reusing information from previous calculations, making it suitable for real-time applications where quick adaptations to changing conditions are essential. This adaptability makes d* particularly valuable in robotic navigation and obstacle avoidance tasks.
Deliberative Obstacle Avoidance: Deliberative obstacle avoidance refers to a systematic approach used in robotics to navigate around obstacles by planning a path that minimizes the chances of collision. This technique relies on algorithms that assess the environment, predict potential obstacles, and determine optimal routes to achieve safe navigation. It emphasizes decision-making processes based on data and reasoning, enabling robotic systems to adapt their movements intelligently in dynamic settings.
Dijkstra's Algorithm: Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights, producing a shortest path tree. This algorithm is widely used in various applications, especially in robotics, for efficient path planning and obstacle avoidance. It finds the least-cost path from a start node to all other nodes, making it crucial for real-time decision making and adaptive mission planning.
Dynamic obstacles: Dynamic obstacles refer to objects or entities in the environment that can change their position or state over time, making navigation and path planning more complex. These obstacles can include moving vehicles, marine life, or even changes in water currents, all of which require adaptive strategies in obstacle avoidance algorithms to ensure safe and efficient movement.
Dynamic window approach: The dynamic window approach is a real-time algorithm used for mobile robot path planning and obstacle avoidance, focusing on selecting the best velocity for the robot while considering its current position and the surrounding environment. It evaluates possible movements based on the robot's dynamics, potential velocities, and obstacles in its path to generate a safe and efficient trajectory. This method allows robots to react quickly to changes in their environment, making it particularly useful for autonomous navigation.
Elevation grids: Elevation grids are structured representations of terrain data that map the height of the surface at various points, typically using a grid format. These grids provide essential information for analyzing topography and are crucial for navigation, simulation, and path planning in robotics. By quantifying elevation changes across a landscape, elevation grids enable more effective obstacle detection and avoidance strategies.
Environment changes: Environment changes refer to the variations in conditions or obstacles in a given area that can affect the performance and navigation of underwater robotics. These changes can include factors like water currents, visibility, temperature fluctuations, and the presence of unexpected obstacles, all of which need to be accounted for during path planning and obstacle avoidance to ensure successful operation.
Gazebo: In the context of robotics and simulation, a gazebo is a powerful 3D simulation tool that provides an environment for testing algorithms, especially for path planning and obstacle avoidance. It allows developers to visualize and simulate complex scenarios with realistic physics, enabling them to refine their navigation strategies without risking damage to physical hardware. This visualization is critical for optimizing performance in real-world applications.
Global path planning: Global path planning is the process of determining an optimal route for a robot or autonomous vehicle from a start point to a destination, taking into consideration the entire environment and potential obstacles. This method typically uses maps or models of the surroundings to find the best possible path, ensuring that the robot can navigate effectively and efficiently. It integrates various algorithms and heuristics to balance factors like distance, safety, and time.
Grid-based path planning: Grid-based path planning is a method used in robotics and computer science for navigating an environment by representing it as a grid or a lattice. Each cell in the grid can either be free space or an obstacle, allowing algorithms to calculate the best route from a starting point to a target while avoiding obstacles. This approach simplifies the complexity of navigation and is particularly useful in environments where precise movement is crucial.
Kalman Filters: Kalman filters are mathematical algorithms used for estimating the state of a dynamic system from a series of noisy measurements. They work by combining predictions from a model of the system with new measurement data, allowing for improved accuracy and reduced uncertainty in tracking objects over time. This technique is especially relevant in robotics for path planning and obstacle avoidance, as it helps robots understand their position and navigate effectively in complex environments.
Local path planning: Local path planning is a crucial process in robotics that involves determining a feasible path for a robot to navigate from its current position to a desired target while avoiding obstacles in its immediate environment. This process requires real-time data and responsiveness, as it enables robots to adapt to changes in their surroundings, making it essential for applications like underwater robotics where dynamic obstacles can occur.
Lpa*: lpa* is an advanced path planning algorithm used for finding optimal paths in environments with obstacles, combining features from both A* and Dijkstra's algorithms. This algorithm enhances pathfinding efficiency by minimizing computational complexity while ensuring that the paths generated are optimal and avoid collisions, making it highly applicable in robotics and autonomous navigation.
Memory usage: Memory usage refers to the amount of memory resources consumed by a program or algorithm during its execution. In the context of robotics, especially for path planning and obstacle avoidance algorithms, efficient memory usage is crucial as it directly impacts the performance and responsiveness of the system. High memory consumption can lead to slower processing times, reduced efficiency, and potential system crashes, making it essential to optimize algorithms to use memory effectively.
Occupancy grids: Occupancy grids are a method used in robotics and computer vision for representing the environment in a grid format, where each cell indicates whether it is occupied by an obstacle or free space. This representation simplifies the process of navigating through an environment by allowing algorithms to quickly assess the location of obstacles and plan paths accordingly. By transforming spatial information into a structured format, occupancy grids enhance the efficiency of path planning and obstacle avoidance algorithms.
Particle Filters: Particle filters are a set of algorithms used for estimating the state of a dynamic system by representing the probability distribution of that state with a finite number of random samples, known as particles. These filters are particularly useful in scenarios where the system's dynamics are nonlinear and the noise is non-Gaussian, making them well-suited for applications such as path planning and obstacle avoidance in robotics.
Path Length: Path length refers to the total distance that an autonomous vehicle or robotic system travels along a designated route from a starting point to a destination. This concept is crucial in the design and implementation of navigation systems, as it influences efficiency, energy consumption, and overall performance when maneuvering through environments that may contain obstacles.
Potential Field Method: The potential field method is a navigation technique used in robotics where a virtual force field is created to guide a robot towards its target while avoiding obstacles. In this approach, attractive forces draw the robot towards its goal, while repulsive forces push it away from obstacles, allowing for dynamic path planning and real-time obstacle avoidance.
Probabilistic Roadmaps (PRM): Probabilistic roadmaps are a path planning method used in robotics, especially for navigating through high-dimensional spaces with obstacles. This technique builds a roadmap by randomly sampling configurations in the environment, connecting them to form a graph that represents possible paths. The PRM is particularly effective in situations where the environment is complex and uncertain, as it allows robots to plan paths efficiently while avoiding obstacles.
Probability roadmap method: The probability roadmap method is a technique used in robotics for path planning that employs probabilistic algorithms to generate and evaluate possible paths in a complex environment. This method combines elements of random sampling and statistical analysis to create a roadmap that outlines viable routes while effectively navigating around obstacles. It is especially valuable in scenarios where the environment is uncertain or dynamic, as it helps robots make informed decisions based on the likelihood of encountering obstacles.
Rapidly-exploring random trees (RRT): Rapidly-exploring random trees (RRT) is a path planning algorithm designed for efficiently searching high-dimensional spaces by incrementally building a tree rooted at the starting point. It works by randomly sampling points in the space and extending the tree towards these points, enabling effective navigation around obstacles. This approach is particularly useful for robotic motion planning, as it allows for real-time obstacle avoidance while exploring complex environments.
Reactive Obstacle Avoidance: Reactive obstacle avoidance is a real-time navigation strategy used by robots and autonomous vehicles to detect and respond to obstacles in their environment as they encounter them. This approach relies on sensor data to make immediate adjustments to the robot's path, ensuring that it can maneuver around obstacles without pre-planning an entire route. By focusing on immediate threats, reactive obstacle avoidance enhances the robot's ability to operate safely and efficiently in dynamic environments.
Robustness: Robustness refers to the ability of a system to maintain its performance and reliability in the face of uncertainties, disturbances, and varying conditions. This concept is crucial in engineering and robotics, as it ensures that systems can operate effectively despite changes in the environment or unexpected challenges. A robust system is characterized by its resilience, adaptability, and overall stability, making it essential for technologies that must function reliably in dynamic or unpredictable situations.
Sampling-based path planning: Sampling-based path planning is a method used in robotics to find a feasible path from a start point to a target point while navigating around obstacles. This approach uses random samples of the environment to construct a path by exploring different configurations and avoiding collisions, making it especially useful in complex, high-dimensional spaces. By generating a network of possible paths, this method can efficiently solve planning problems that are difficult for traditional algorithms.
Sensor noise and errors: Sensor noise and errors refer to the inaccuracies and random variations in the readings provided by sensors used in underwater robotics. These discrepancies can result from various factors including environmental conditions, sensor limitations, and electronic interference. Understanding and managing sensor noise and errors is crucial for effective path planning and obstacle avoidance algorithms, as they directly affect the reliability of data used to make navigation decisions.
Uwsim: uwsim is a simulation tool specifically designed for underwater robotic systems, allowing users to test and develop algorithms in a virtual environment. This platform enables researchers and engineers to create realistic simulations of underwater vehicles, helping them optimize path planning and obstacle avoidance strategies without the risks and costs associated with physical trials.
Vector field histogram method: The vector field histogram method is a technique used for path planning and obstacle avoidance, particularly in robotic navigation. It works by creating a histogram representation of the environment, where each cell in the grid reflects the density of obstacles around the robot. This approach allows the robot to determine safe paths by analyzing the distribution of obstacles and selecting directions that minimize collision risk.
Visibility: Visibility refers to the distance and clarity with which objects can be seen in an aquatic environment, significantly influenced by factors like water clarity, light penetration, and the presence of particulates. In underwater robotics, visibility is crucial as it impacts the ability of autonomous vehicles to navigate and identify obstacles in their path. The quality of visibility determines how effectively path planning and obstacle avoidance algorithms can function, as well as how operators perceive and interact with the marine environment.
© 2024 Fiveable Inc. All rights reserved.
AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.
Back
Practice QuizGlossary
Practice QuizGlossary
Next guide