Introduction
An autonomous system must determine how to move from its current position to a destination without colliding with obstacles or violating operational constraints. This process involves path planning and obstacle avoidance.
Path planning determines a suitable route through the environment. Obstacle avoidance modifies or controls movement so that the autonomous platform remains safely separated from objects, people, vehicles, walls, terrain, and restricted regions.
A self-driving vehicle must calculate a route through a road network, follow the correct lane, avoid surrounding traffic, and respond to unexpected road hazards. A warehouse robot must navigate through corridors while avoiding shelves, workers, forklifts, and other robots. A drone must calculate a three-dimensional flight path around buildings, trees, power lines, and restricted airspace.
The shortest geometric path is not always the safest or most useful path. Autonomous systems must also consider vehicle dimensions, turning radius, speed, acceleration, braking distance, energy use, surface condition, traffic rules, uncertainty, and movement of other objects.
Path-planning and obstacle-avoidance algorithms therefore solve several connected problems. They determine where the system should move, whether the route is physically feasible, how the system should respond to changing obstacles, and when a new route must be calculated.
The overall process can be represented as:
Current Pose → Map and Sensor Data → Free-Space Representation → Global Path Planning → Local Obstacle Avoidance → Trajectory Generation → Motion Control → Continuous Replanning
Path, Route, and Trajectory
A path is a geometric sequence of positions connecting a starting point and a destination.
A route is often a higher-level sequence of roads, corridors, regions, or waypoints.
A trajectory includes both position and time. It specifies where the autonomous system should be located at each moment and may also include speed, acceleration, heading, and steering information.
A ground robot may have a path consisting of several points through a building. Its trajectory determines how quickly it should move between those points.
A self-driving vehicle requires a time-based trajectory because surrounding traffic is moving. The system must determine not only where to pass but also when it will occupy each position.
A drone trajectory includes horizontal position, altitude, orientation, velocity, and time.
Path planning mainly considers spatial feasibility. Trajectory planning additionally considers dynamic and timing constraints.
Configuration Space
An autonomous platform occupies physical space. It cannot be treated as a single mathematical point when checking for collision.
Configuration space represents the possible positions and orientations of the platform.
A small circular robot moving on a flat floor may be represented by its horizontal position. A vehicle may require position and heading because its orientation affects whether it can turn through a narrow region.
A robotic arm has a higher-dimensional configuration space because each joint angle affects its physical shape.
Obstacle regions can be expanded according to the dimensions of the autonomous platform. The platform can then be treated as a point while planning through the remaining free space.
This expansion is known as configuration-space obstacle construction or obstacle inflation.
If a robot has a radius of thirty centimetres, walls and objects are expanded by at least that amount in the planning map. The robot’s centre is then prevented from entering the inflated regions.
Additional inflation may be applied to account for localization error, control error, speed, and uncertainty.
Free Space, Occupied Space, and Unknown Space
Planning algorithms require a representation of where movement is possible.
Free space contains regions believed to be safe for movement.
Occupied space contains detected obstacles, walls, structures, restricted regions, or terrain that the autonomous platform cannot cross.
Unknown space contains regions that have not been observed sufficiently.
Unknown space should not automatically be treated as free. A sensor may not have observed the area because it lies behind an object, outside the field of view, or beyond the sensor range.
Some systems avoid unknown space completely. Exploration systems may enter unknown regions cautiously while continuously mapping them.
The planning behaviour depends on the mission. A warehouse delivery robot normally uses known free space. A search-and-rescue robot may need to explore unknown areas while maintaining a safe return route.
Global and Local Path Planning
Autonomous navigation usually separates planning into global and local components.
The global planner uses a complete or large-scale map to calculate the main route from the current location to the destination.
It may select roads, corridors, rooms, intersections, or broad regions.
The local planner uses current sensor data to follow the global route while responding to nearby obstacles and environmental changes.
A global map may show that a warehouse corridor is open. During operation, a temporary pallet may block that corridor. The local planner attempts to move around the pallet. If this is not possible, the system requests a new global route.
A self-driving vehicle may receive a global route consisting of several roads. Its local planner calculates a safe trajectory within the current lane and around nearby vehicles.
Global planning supports long-distance direction. Local planning provides immediate safety and adaptation.
Planning in Static and Dynamic Environments
A static environment contains obstacles whose positions do not change during planning and movement.
Walls, permanent shelves, buildings, and road boundaries may be treated as static.
A dynamic environment contains moving or changing obstacles.
Pedestrians, vehicles, robots, animals, machinery, and drones are dynamic obstacles.
Temporary objects may also appear or disappear.
Static planning determines whether a geometric route avoids fixed obstacles. Dynamic planning must consider where obstacles will be in the future.
A route that is spatially clear may still be unsafe if a moving obstacle will occupy the same location at the same time.
Dynamic navigation therefore requires tracking, movement prediction, time-dependent planning, and continuous replanning.
Graph-Based Path Planning
Many path-planning algorithms represent the environment as a graph.
A graph contains nodes and edges.
Nodes represent locations or states. Edges represent possible movement between them.
A road network may use intersections as nodes and roads as edges.
An occupancy grid can be converted into a graph in which each free cell is connected to neighbouring cells.
The cost of an edge may represent distance, travel time, energy use, terrain difficulty, congestion, or risk.
The planner searches the graph for a sequence of connected nodes with minimum total cost.
Graph-based methods are widely used because they are systematic, understandable, and capable of producing optimal or near-optimal routes under defined assumptions.
Grid-Based Planning
A grid map divides the environment into square or rectangular cells.
Each cell is classified as free, occupied, or unknown.
The robot moves between neighbouring free cells.
In a four-connected grid, movement is allowed horizontally and vertically.
In an eight-connected grid, diagonal movement is also permitted.
A finer grid provides more precise obstacle boundaries and paths but increases memory and search time.
A coarse grid reduces computation but may remove narrow passages or generate inaccurate routes.
The selected resolution should reflect platform size, sensor accuracy, environment size, and planning requirements.
Grid-based planning is commonly used with Dijkstra’s algorithm, A-star, D-star, and related search methods.
Dijkstra’s Algorithm
Dijkstra’s algorithm finds the lowest-cost path from a starting node to all reachable nodes or to a selected destination.
The algorithm begins at the start node with zero accumulated cost.
It examines neighbouring nodes and records the cost required to reach each one.
The unexplored node with the lowest accumulated cost is selected next.
This process continues until the destination is reached.
Dijkstra’s algorithm guarantees the optimal path when all movement costs are non-negative.
In a simple grid where every movement has equal cost, it finds the shortest route.
If cells contain different costs, it finds the route with the lowest total cost.
A robot may assign higher cost to narrow corridors, rough terrain, crowded regions, or locations near obstacles.
Dijkstra’s algorithm is reliable and complete, meaning that it will find a path when one exists within the represented graph.
Its main limitation is that it explores in all directions. In a large map, it may examine many locations that do not lead toward the destination.
A-Star Algorithm
A-star improves graph search by using a heuristic estimate of the remaining cost to the destination.
The algorithm evaluates each node using two quantities.
The first is the actual cost from the start to the current node.
The second is the estimated cost from the current node to the goal.
The combined value guides the search toward the destination.
The evaluation can be represented as:
Estimated Total Cost = Cost Already Travelled + Estimated Remaining Cost
The heuristic may use Euclidean distance, Manhattan distance, diagonal distance, or another estimate suitable for the environment.
When the heuristic does not overestimate the true remaining cost, A-star can still guarantee an optimal path.
A-star normally explores fewer nodes than Dijkstra’s algorithm because it focuses more strongly on the goal direction.
It is widely used for autonomous robots, games, road navigation, and occupancy-grid planning.
The result depends on map quality and resolution. A-star may generate sharp turns and paths that pass close to obstacles unless additional costs and smoothing are applied.
Weighted A-Star
Weighted A-star increases the influence of the heuristic.
This makes the search move more aggressively toward the destination and often reduces computation.
However, the resulting path may not be perfectly optimal.
For real-time autonomous systems, a slightly longer route produced quickly may be more useful than a mathematically shortest path that requires excessive processing.
The selected weight controls the balance between search speed and path optimality.
Weighted A-star is useful when rapid planning is more important than guaranteeing the absolute minimum route cost.
D-Star and Dynamic Replanning
D-star algorithms are designed for environments where the map may change during movement.
A robot may initially plan through a corridor believed to be clear. When sensors detect an unexpected obstacle, the movement cost of that area changes.
Instead of calculating the entire route again from the beginning, D-star updates the affected part of the search.
D-star Lite is a widely used simplified version.
These algorithms are useful for outdoor exploration, planetary rovers, search-and-rescue robots, and systems moving through partially known environments.
Incremental replanning reduces computation when only part of the map changes.
The planner still depends on timely obstacle detection and a valid updated map.
Lifelong Planning A-Star
Lifelong Planning A-star is another incremental-search method.
It reuses information from previous A-star searches.
When movement costs change, it updates only the nodes affected by the modification.
This is useful when an autonomous system repeatedly plans through a map that changes gradually.
The method can reduce planning time compared with restarting the search after every environmental change.
Incremental planners are especially valuable for large maps and frequent updates.
Theta-Star
Grid-based A-star normally restricts movement to connections between neighbouring cell centres.
This can produce paths containing unnecessary turns.
Theta-star allows the planner to connect a node directly to a more distant ancestor when there is a clear line of sight.
The resulting path can move at arbitrary angles rather than following only grid directions.
This produces shorter and smoother routes.
Theta-star remains based on graph search but reduces the artificial shape created by the grid.
Line-of-sight checks require additional computation, and the resulting path must still be checked against vehicle dynamics and safety margins.
Jump Point Search
Jump Point Search accelerates path planning on uniform-cost grids.
Instead of evaluating every cell individually, it skips across sequences of cells until it reaches important turning or branching points.
This reduces the number of explored nodes while preserving optimality under suitable conditions.
Jump Point Search is particularly effective in large open grid maps with uniform movement costs.
Its benefits decrease when the map contains highly varied costs or complex non-grid constraints.
Roadmap-Based Planning
Roadmap methods create a network of possible routes through continuous space.
Instead of evaluating every point in the environment, they represent selected locations and connections.
Visibility graphs, Voronoi diagrams, Probabilistic Roadmaps, and Rapidly Exploring Random Trees are important examples.
Roadmap-based methods are useful in continuous and high-dimensional spaces where simple grids become computationally expensive.
Visibility Graphs
A visibility graph uses obstacle vertices as graph nodes.
Two nodes are connected when a straight line between them does not cross an obstacle.
The start and goal are also included.
The shortest path through the graph often follows obstacle boundaries.
Visibility graphs can produce geometrically shortest paths for polygonal obstacles.
However, these paths may pass extremely close to corners and walls.
An autonomous platform requires clearance, so obstacles must be inflated or the path must be modified.
Visibility graphs also become complex when the environment contains many obstacles.
They are best suited to known environments with clearly represented polygonal geometry.
Voronoi Diagrams
A Voronoi-based planner creates routes that remain approximately equally distant from nearby obstacles.
The path tends to follow the middle of free corridors.
This provides strong clearance and can improve safety.
However, the route may be longer than the geometrically shortest path.
Voronoi methods are useful when maintaining distance from obstacles is more important than minimizing travel distance.
A mobile robot navigating through uncertain or narrow environments may benefit from the larger safety margin.
The final route can combine Voronoi clearance with optimization toward the destination.
Probabilistic Roadmaps
A Probabilistic Roadmap samples collision-free configurations from the environment.
The samples become roadmap nodes.
Nearby nodes are connected when a collision-free local path exists between them.
After the roadmap is built, the start and goal are connected to it, and a graph-search algorithm finds a route.
Probabilistic Roadmaps are useful for repeated planning in the same environment.
A robotic arm may use one roadmap to calculate movements for many start and target configurations.
The construction stage may require significant processing, but future route queries are faster.
The method is probabilistically complete. As more samples are added, the probability of finding a path increases when one exists.
However, narrow passages may be missed unless sampling is sufficiently dense or guided toward difficult regions.
Rapidly Exploring Random Trees
Rapidly Exploring Random Trees, commonly called RRT, are sampling-based planning methods.
An RRT begins at the start configuration.
The algorithm repeatedly samples a random point and extends the existing tree toward it.
The tree naturally expands into unexplored regions.
When it reaches the goal or connects sufficiently close to it, a route can be extracted.
RRT is useful in continuous and high-dimensional configuration spaces.
It is widely used for robotic arms, drones, autonomous vehicles, and systems with complex motion constraints.
The basic RRT algorithm finds feasible paths efficiently but does not guarantee the shortest path.
The result may contain unnecessary turns and require smoothing.
Bidirectional RRT
Bidirectional RRT grows one tree from the start and another from the goal.
The planner attempts to connect the two trees.
Searching from both directions often reduces planning time.
This method is useful when the goal configuration is clearly defined and collision checks can be performed from both directions.
The approach may be less suitable when system dynamics make reverse expansion difficult or when the goal region is uncertain.
RRT-Star
RRT-star extends RRT to improve path quality.
When a new sample is added, the planner evaluates whether connecting it through a different nearby node would reduce total cost.
It also rewires existing parts of the tree when a better connection becomes available.
As the number of samples increases, RRT-star approaches the optimal path under suitable assumptions.
This produces better routes than basic RRT but requires more computation.
RRT-star is useful when both complex geometry and path quality are important.
Informed RRT-Star
Informed RRT-star improves search after an initial solution is found.
It restricts further sampling to the region that could contain a better path.
This reduces wasted samples in irrelevant areas.
The algorithm can improve path quality more efficiently than unrestricted RRT-star.
It is valuable for complex continuous-space planning where an initial feasible path must be found quickly and then refined.
Kinodynamic Planning
Geometric planning determines whether a path avoids obstacles, but it may ignore how the system actually moves.
Kinodynamic planning considers both kinematic and dynamic constraints.
Kinematic constraints include turning radius, steering angle, and movement direction.
Dynamic constraints include velocity, acceleration, force, momentum, and braking ability.
A car cannot move sideways or turn instantly. A drone cannot change velocity without acceleration. A robotic arm has limits on joint speed and torque.
Kinodynamic planners search through possible states and control actions rather than only spatial positions.
Variants of RRT and optimization-based methods are often used for these problems.
The resulting trajectory is more likely to be physically executable.
Non-Holonomic Constraints
A non-holonomic system cannot move freely in every direction.
A car can move forward and backward but cannot move directly sideways.
Its current heading affects which future positions are reachable.
A conventional grid path may include sharp ninety-degree turns that a car cannot follow.
Vehicle planning must consider minimum turning radius, steering limits, and forward or reverse motion.
Algorithms such as Hybrid A-star include heading and vehicle motion models in the search.
Hybrid A-Star
Hybrid A-star combines discrete graph search with continuous vehicle motion.
The state includes position and orientation.
Instead of moving only between neighbouring grid cells, the algorithm uses short feasible vehicle motions generated from steering commands.
This allows it to produce paths that respect non-holonomic constraints.
Hybrid A-star is commonly used for autonomous vehicles, parking systems, and car-like robots.
It may include forward and reverse movements, making it suitable for manoeuvres in limited spaces.
The generated path often requires smoothing and further trajectory optimization.
Reeds–Shepp and Dubins Paths
Dubins paths describe shortest paths for a forward-moving vehicle with a limited turning radius.
The path consists of straight segments and circular arcs.
Reeds–Shepp paths extend this concept to vehicles that can move both forward and backward.
These methods are useful for car-like robots, parking, and local manoeuvre generation.
They assume simplified vehicle geometry and may not account directly for obstacles, acceleration, or moving objects.
They are often used as local connection methods within larger planning algorithms.
Cost Functions
Path planning requires a way to compare possible routes.
A cost function assigns a numerical value to a path or trajectory.
Distance is one possible cost, but autonomous systems normally consider several factors.
Travel time, energy consumption, obstacle clearance, terrain condition, road rules, smoothness, steering effort, passenger comfort, communication quality, and uncertainty may all influence cost.
The total cost may be represented as a weighted combination of these terms.
The weights determine the relative importance of each objective.
A high obstacle-clearance weight creates safer but possibly longer paths.
A high time weight creates faster routes but may reduce comfort or energy efficiency.
Safety constraints should not always be treated as costs that can be traded against efficiency. Critical collision and legal limits are often implemented as hard constraints.
Cost Maps
A cost map represents the navigation cost of different environmental regions.
Occupied cells have extremely high or infinite cost.
Free cells have lower cost.
Areas near obstacles may receive gradually increasing costs.
This encourages the planner to remain near the centre of open space rather than moving directly beside a wall.
Different terrain types may have different costs. Smooth floor may be inexpensive, while gravel, mud, or steep slopes receive higher cost.
Crowded areas may receive additional social cost.
The cost map connects perception with planning by converting environmental understanding into movement preferences.
Static and Dynamic Cost Maps
A static cost map contains permanent environmental information such as walls, roads, shelves, and fixed restricted regions.
A dynamic cost map contains temporary information from current sensors.
People, vehicles, packages, and changing obstacles appear in the dynamic layer.
The planner combines both layers.
A robot may know from its static map that a corridor exists, while its dynamic map indicates that the corridor is temporarily blocked.
Keeping static and dynamic information separate prevents temporary objects from permanently changing the map.
Obstacle Avoidance
Obstacle avoidance is the process of changing movement to prevent collision.
Global planners may avoid mapped obstacles, but local avoidance is required for unexpected and moving objects.
A local avoidance algorithm receives current obstacle positions, platform motion, and goal direction.
It produces a steering command, local path, or short trajectory.
Obstacle avoidance must operate quickly because nearby conditions can change rapidly.
The method should also avoid unstable behaviour such as repeated left-right turning or stopping unnecessarily.
Reactive Obstacle Avoidance
Reactive methods select movement directly from current sensor measurements.
They do not require a complete global map.
A robot may turn toward open space detected by LiDAR or ultrasonic sensors.
Reactive methods are computationally efficient and respond quickly.
However, they may become trapped because they do not consider the complete route.
A robot may avoid a U-shaped obstacle by moving deeper into it because the immediate direction appears open.
Reactive avoidance is therefore commonly combined with global planning.
Bug Algorithms
Bug algorithms are simple navigation methods designed for robots with limited environmental knowledge.
The robot moves directly toward the goal until it encounters an obstacle.
It then follows the obstacle boundary until it finds a suitable point to continue toward the goal.
Bug 1 follows the entire obstacle boundary, identifies the point closest to the goal, and then moves to that point.
Bug 2 follows the boundary until it reaches the line connecting the start and goal at a point closer to the goal.
These methods are simple and can guarantee reaching the goal under certain assumptions.
However, their paths may be long and inefficient.
They are mainly useful for understanding reactive navigation principles and for simple low-cost robots.
Artificial Potential Fields
Artificial Potential Field methods treat the destination as an attractive force and obstacles as repulsive forces.
The attractive force pulls the robot toward the goal.
The repulsive forces push it away from obstacles.
The combined force determines the movement direction.
This method is intuitive and computationally efficient.
It produces smooth local motion and responds continuously to obstacle distance.
However, the robot may become trapped in a local minimum where attractive and repulsive forces balance.
It may also oscillate in narrow passages or struggle when an obstacle lies directly in front of the goal.
Improved methods add random movement, intermediate goals, navigation functions, or global-planner guidance to reduce these problems.
Vector Field Histogram
The Vector Field Histogram method uses range-sensor data to create a representation of obstacle density around the robot.
The environment is divided into angular sectors.
Each sector receives a value representing how strongly obstacles block that direction.
The algorithm identifies open sectors and selects one that moves the robot toward the goal while maintaining clearance.
Vector Field Histogram methods are efficient and suitable for real-time mobile-robot navigation.
They manage noisy sensor measurements better than simple potential fields.
However, they may still produce oscillation and require careful parameter selection for robot size, speed, and environmental density.
Follow-the-Gap Method
The Follow-the-Gap method identifies open gaps among obstacles using range measurements.
The algorithm selects a suitable gap and directs the system through it.
It is often used in fast mobile robots and autonomous racing applications because it is computationally lightweight.
The selected gap may be based on width, direction toward the goal, and distance from obstacle boundaries.
The method provides effective local avoidance but does not replace global planning.
Without a global route, the robot may enter open areas that do not lead toward the destination.
Dynamic Window Approach
The Dynamic Window Approach evaluates short-term velocity commands.
For a differential-drive robot, the candidate commands normally include linear and angular velocity.
The algorithm considers only velocities that the robot can reach within its acceleration limits.
Each command is simulated over a short future interval.
The resulting trajectory is checked for collision.
Safe trajectories are scored according to progress toward the goal, alignment with the global path, obstacle clearance, and speed.
The highest-scoring command is selected.
Because the method considers acceleration and braking, it produces dynamically feasible movement.
The Dynamic Window Approach is widely used in indoor mobile robots and ROS navigation systems.
Its behaviour depends strongly on parameters. Excessive obstacle weighting may make the robot overly cautious. Excessive goal weighting may cause it to pass too close to objects.
Timed Elastic Band Planning
The Timed Elastic Band method represents the local trajectory as a sequence of poses connected by time intervals.
The trajectory is optimized according to obstacle clearance, travel time, smoothness, kinematic limits, velocity, and acceleration.
The band behaves like an elastic structure that is pulled toward the goal and pushed away from obstacles.
Because time is included, the planner can consider velocity and dynamic feasibility.
Timed Elastic Band planning is suitable for car-like, differential-drive, and holonomic robots.
It can produce smooth local trajectories, but optimization may become difficult in crowded or rapidly changing environments.
The planner requires accurate obstacle and robot models.
Model Predictive Control for Obstacle Avoidance
Model Predictive Control uses a model of the autonomous system to predict future movement.
At each update, it considers several possible control sequences over a limited prediction horizon.
The planner evaluates their cost and constraints.
It selects the best initial control action, applies it, receives new sensor data, and repeats the process.
Model Predictive Control can consider steering, speed, acceleration, obstacles, road boundaries, and comfort simultaneously.
It is widely used in autonomous vehicles, drones, and advanced mobile robots.
The method produces dynamically feasible trajectories and can handle multiple constraints explicitly.
Its main limitation is computational demand. Optimization must be completed within the available real-time interval.
The prediction model must also represent system dynamics accurately.
Velocity Obstacles
Velocity-obstacle methods analyse potential collision according to relative motion.
Instead of representing only where an obstacle is currently located, they determine which platform velocities would lead to collision in the future.
Unsafe velocity regions are excluded.
The planner selects a velocity outside these regions that still moves toward the destination.
Velocity Obstacles are useful for moving obstacles and multi-agent navigation.
They assume that the motion of other objects can be estimated over the planning horizon.
Incorrect movement prediction may reduce performance.
Reciprocal Velocity Obstacles
Reciprocal Velocity Obstacles extend the method to situations where several agents adjust their movement cooperatively.
Each agent assumes part of the responsibility for avoiding collision.
Optimal Reciprocal Collision Avoidance is a well-known approach used in multi-robot and crowd navigation.
It selects collision-free velocities while attempting to remain close to each agent’s preferred movement.
The method can produce efficient decentralized coordination.
However, it assumes other agents follow similar avoidance behaviour.
Human pedestrians may not respond according to the same model, so additional prediction and conservative margins are required.
Collision Checking
Every planned path or trajectory must be checked for collision.
A simple method checks whether path points enter occupied cells.
More accurate methods consider the full platform footprint between points.
For a moving vehicle, the swept area of the body along the trajectory should remain free.
Collision checking must include obstacles, map boundaries, restricted zones, and height limitations.
For drones, three-dimensional collision checks must consider objects above, below, and around the platform.
Checking only selected points may miss a collision between them. The sampling interval should therefore reflect speed, curvature, and obstacle size.
Continuous collision-detection methods provide stronger guarantees but require more computation.
Safety Distance
An obstacle-free path should maintain adequate clearance.
The required distance depends on platform size, speed, braking ability, localization uncertainty, obstacle movement, sensor error, and environment.
A slow indoor robot may safely pass closer to a wall than a vehicle travelling at high speed.
Greater uncertainty requires a larger margin.
Moving people should normally receive wider and more conservative safety zones than fixed walls.
Safety distance can be represented through obstacle inflation, cost maps, constraints, or collision-checking rules.
Braking Distance
Obstacle avoidance must consider whether the platform can stop before collision.
Braking distance increases with speed.
It also depends on surface condition, tyre or wheel traction, vehicle mass, actuator capability, slope, and control delay.
A local planner should reject trajectories from which safe stopping is impossible.
The system should maintain sufficient visible and verified free space ahead.
This principle is sometimes described as remaining within a safe stopping region.
A drone requires enough distance and time to reduce velocity or change direction safely.
A robot carrying a heavy load may require a longer stopping distance than the same robot without a load.
Time to Collision
Time to collision estimates how long remains before two moving objects may collide if their current movement continues.
It depends on relative position and velocity.
A small time-to-collision value indicates urgent risk.
The system may use this estimate to reduce speed, change direction, or apply emergency braking.
Time to collision is useful because a distant object moving rapidly toward the platform may be more dangerous than a nearby object moving away.
The calculation may be uncertain when objects change direction or speed.
Prediction and tracking should therefore be updated continuously.
Dynamic Obstacle Prediction
Avoiding moving obstacles requires estimates of their future positions.
Simple models assume constant velocity or constant acceleration.
More advanced models consider road structure, pedestrian pathways, behavioural patterns, and interaction with other agents.
A pedestrian may continue walking, stop, turn, or cross.
A vehicle may change lanes, brake, or accelerate.
The planner may represent several possible future trajectories with probabilities.
Safety regions are expanded according to prediction uncertainty.
The farther into the future the system predicts, the greater the uncertainty usually becomes.
Space–Time Planning
Space–time planning treats time as an additional planning dimension.
A location may be free at one moment and occupied at another.
The planner searches for a trajectory that avoids obstacles across both space and time.
A robot may wait temporarily for a moving obstacle to pass rather than taking a long detour.
A vehicle may adjust speed to merge into an available traffic gap.
Space–time planning is important in dynamic environments but increases computational complexity.
The system requires reliable object tracking and movement prediction.
Multi-Robot Path Planning
When several robots share an environment, their routes can conflict.
Individually shortest paths may cause collisions, deadlocks, or congestion.
Multi-robot planning coordinates movement across the fleet.
A centralized planner considers all robot routes together.
This can produce efficient coordination but becomes computationally difficult as the number of robots increases.
Decentralized methods allow each robot to plan locally while communicating or applying shared movement rules.
Priority-based planning assigns some robots the right to move first.
Reservation-based planning reserves regions or time intervals for particular robots.
Fleet-management systems may also control intersections and one-way corridors.
Deadlocks
A deadlock occurs when two or more autonomous agents prevent one another from moving.
Two robots may face each other in a narrow corridor, with neither able to pass.
A group of robots may block an intersection.
Deadlock prevention may use route priorities, traffic rules, one-way zones, waiting regions, or centralized coordination.
Deadlock detection identifies when progress has stopped for an unusual period.
Recovery may require one robot to reverse, move to a waiting position, or release its reserved route.
Random movement should not be used in narrow or crowded regions without safety checks.
Social Obstacle Avoidance
Navigation around people requires more than physical collision avoidance.
A robot should respect personal space, walking direction, groups, queues, doorways, and social expectations.
Passing directly between two people in conversation may be physically possible but socially inappropriate.
Social cost maps assign higher costs to areas close to people or inside predicted walking paths.
The cost may be larger in front of a person than behind them because people require more space in their direction of movement.
Human-aware planning may also reduce speed and produce clear, predictable trajectories.
Path Smoothing
Search algorithms often produce paths containing sharp turns or unnecessary changes in direction.
Path smoothing creates a more continuous and physically feasible route.
A simple method removes intermediate points when a direct collision-free connection exists.
Polynomial curves, splines, Bezier curves, clothoids, and optimization methods can generate smoother paths.
The smoothed route should remain within free space and preserve safety margins.
Excessive smoothing may cause the path to cut through obstacles or restricted areas.
Vehicles require curvature-continuous paths to avoid sudden steering changes.
Drones and robotic arms require smooth acceleration to maintain stability and reduce mechanical stress.
Trajectory Optimization
Trajectory optimization adjusts the full time-based motion to reduce cost while satisfying constraints.
The optimization may consider obstacle clearance, travel time, acceleration, energy use, comfort, steering effort, and dynamic feasibility.
The trajectory is represented through control points, states, or control commands.
The solver modifies these variables until it finds a suitable solution.
Optimization-based planning can produce high-quality motion.
However, it may converge to a local solution rather than the best global path.
It also requires an initial guess and sufficient computation.
A common architecture uses a graph or sampling planner to find an initial route and then applies optimization to improve it.
Replanning Frequency
The system must determine how often to update its plan.
Frequent replanning allows rapid response to new obstacles but increases computation and may create unstable changes.
Infrequent replanning reduces processing but may allow the plan to become outdated.
Local planning normally runs more frequently than global planning.
A mobile robot may update local movement several times per second while recalculating the global route only when necessary.
A fast autonomous vehicle requires higher update rates.
The system should also trigger immediate replanning when a critical obstacle, localization failure, or route blockage is detected.
Planning Horizon
The planning horizon describes how far into the future the system considers.
A short horizon improves immediate responsiveness but may produce poor long-term choices.
A robot may avoid a nearby obstacle in a way that leads into a dead end.
A long horizon improves strategic planning but requires more prediction and computation.
Uncertainty also increases farther into the future.
Many systems combine a long-range global planner with a short-range local planner.
Model Predictive Control repeatedly solves a limited-horizon problem using new observations, allowing it to combine prediction and feedback.
Planning Under Uncertainty
Maps, sensor measurements, localization, and obstacle predictions are uncertain.
A path that appears clear may contain an undetected object.
A moving obstacle may change direction.
The autonomous platform’s actual position may differ from its estimate.
Uncertainty-aware planning increases safety margins and may prefer routes with better visibility or more open space.
A slightly longer route through a wide corridor may be preferable to a narrow route when localization confidence is low.
Probabilistic planners represent the likelihood of occupancy, collision, or future movement.
Risk-sensitive planning considers both probability and consequence.
Chance-Constrained Planning
Chance constraints require the probability of violating a safety condition to remain below a selected limit.
Instead of assuming that obstacle position is exact, the system represents a distribution of possible positions.
The planned trajectory must maintain an acceptably low collision probability.
This approach is useful when sensor and prediction uncertainty can be estimated.
Selecting the permitted probability level is a safety and policy decision.
A very strict limit creates cautious behaviour, while a relaxed limit may improve efficiency but increase risk.
Robust Planning
Robust planning attempts to produce paths that remain safe across a range of possible conditions.
The planner may consider worst-case localization error, control error, obstacle movement, or wind disturbance.
A drone path may maintain greater distance from a building to account for wind.
A vehicle may increase lane-boundary clearance during poor visibility.
Robust planning can reduce sensitivity to modelling errors but may produce conservative routes.
The level of conservatism should reflect the consequences of failure.
Learning-Based Path Planning
Machine-learning methods can support or generate navigation behaviour.
A model may predict route cost, obstacle movement, drivable space, or suitable local actions.
Reinforcement-learning policies may learn obstacle avoidance through simulation.
Neural planners may map sensor input to movement commands.
Learning-based methods can manage complex environmental patterns.
However, they depend on training data and may fail in unfamiliar conditions.
They may also be difficult to explain and verify.
For safety-critical systems, learning-based recommendations are commonly combined with conventional planners and rule-based safety checks.
Reinforcement Learning for Local Navigation
A reinforcement-learning agent may receive obstacle distances, goal direction, current speed, and local map information.
It selects actions such as moving forward, turning, slowing, or stopping.
The reward encourages progress, collision avoidance, smooth motion, and energy efficiency.
Training can occur in simulated environments containing many obstacle arrangements.
The resulting policy may adapt well to dynamic situations.
However, it may exploit weaknesses in the reward or simulator.
A safety layer should reject actions that violate minimum distance, speed, or stopping constraints.
End-to-End Navigation
End-to-end navigation maps raw sensor input directly to steering or movement commands.
A neural network may receive a camera image and produce steering and speed.
This approach can learn complex behaviour with limited manually designed processing.
However, it combines perception, planning, and control inside one model.
Failure analysis becomes difficult because the source of an incorrect action may not be clear.
The system may also produce unpredictable behaviour when environmental conditions differ from the training data.
Modular architectures are generally easier to validate and maintain.
Hybrid Planning Architectures
A hybrid planner combines several methods.
A global A-star planner may calculate the main route.
A local Dynamic Window or Timed Elastic Band planner may avoid immediate obstacles.
A Model Predictive Controller may generate dynamically feasible commands.
A reinforcement-learning model may predict pedestrian movement or local congestion.
A rule-based safety layer may reject unsafe actions.
This layered structure allows each method to perform the task for which it is best suited.
It also provides redundancy and clearer system responsibility.
Emergency Obstacle Avoidance
Normal local planning may not respond quickly enough when a collision becomes immediately possible.
An emergency layer monitors distance, relative speed, time to collision, and braking capability.
It can override the normal planner.
A vehicle may apply emergency braking.
A drone may perform rapid deceleration, climb, or emergency landing.
A robot may stop all movement.
Emergency behaviour should be simple, predictable, and independently tested.
It should not rely entirely on a complex learning model.
The emergency response must also consider secondary risks. Sudden stopping may be dangerous for a high-speed vehicle if another vehicle is following closely.
Recovery from Planning Failure
A planner may fail to find a path even when movement may still be possible.
The map may contain temporary noise, the goal may lie too close to an obstacle, or the robot may be trapped in a local minimum.
Recovery actions may include clearing short-term obstacle data, rotating to collect new sensor information, moving backward, requesting a new global route, or selecting a nearby temporary goal.
If the environment remains blocked, the system may wait, return to a safe location, or request human assistance.
Recovery should not involve unverified random movement.
The system should record the cause of repeated failure for maintenance and analysis.
Path-Planning Evaluation
Path-planning performance can be evaluated using route length, travel time, computation time, success rate, obstacle clearance, energy consumption, smoothness, and number of replanning events.
A mathematically short path may perform poorly if it passes too close to obstacles or requires sharp turns.
A highly safe path may be inefficient if it is unnecessarily long.
The evaluation should reflect the intended application.
A warehouse robot may prioritize task completion and congestion avoidance.
A passenger vehicle must also consider comfort and legal compliance.
A drone must consider energy reserve and safe landing options.
Obstacle-Avoidance Evaluation
Obstacle avoidance can be evaluated through collision rate, minimum distance, response time, path deviation, oscillation, stopping behaviour, and success in crowded environments.
Testing should include static obstacles, moving obstacles, sudden appearances, sensor noise, partial occlusion, and unpredictable movement.
The system should also be tested when obstacles block the complete route.
A good local planner should not repeatedly attempt to pass through an impossible region.
It should identify when global replanning or human assistance is required.
Simulation Testing
Simulation allows planners to be tested across many maps and obstacle conditions.
Rare and dangerous scenarios can be created safely.
Vehicles can be tested with sudden road blockage, pedestrian crossing, sensor failure, and difficult traffic.
Robots can be tested in narrow corridors, dense crowds, and changing warehouse layouts.
Drones can be tested with wind, moving obstacles, and emergency landing conditions.
Simulation supports rapid comparison among algorithms.
However, physical testing remains necessary because real sensors, actuators, surfaces, delays, and human behaviour are more complex.
Physical Validation
Physical testing should begin in controlled environments.
Movement speed and operating area should be limited.
Emergency stopping and human supervision should remain available.
Testing should gradually include narrow spaces, moving obstacles, poor visibility, localization error, and sensor degradation.
The complete system should be evaluated from perception through control.
A path may be correct in software but unsafe when actuator delay or wheel slip is included.
Computational Requirements
Planning algorithms must produce results within the available time.
Large maps, high-dimensional states, dynamic obstacles, and long prediction horizons increase computation.
Graph search may be accelerated using efficient data structures, hierarchical maps, and reduced-resolution planning.
Sampling methods may use parallel collision checking.
Optimization methods may use warm starts from previous solutions.
Local planners should operate on a limited region near the platform rather than the complete global map.
Dedicated processors and hardware acceleration may support complex autonomous vehicles and drones.
Hierarchical Planning
Hierarchical planning represents the environment at several levels.
A high-level planner selects broad regions, roads, or rooms.
A lower-level planner calculates precise movement within the selected region.
This reduces search complexity.
A vehicle route planner may select highways and streets. A lane-level planner then selects the appropriate lane and trajectory.
A building robot may first select a sequence of rooms and corridors, then generate local movements.
Hierarchical planning also supports task-level decisions such as whether to deliver, recharge, wait, or return.
Path Planning in Autonomous Cars
Autonomous cars use road-network planning, lane-level planning, behaviour selection, and trajectory generation.
The global planner selects a legal road route.
The behaviour planner determines whether to follow, yield, stop, turn, or change lanes.
The trajectory planner calculates a smooth path that respects lane boundaries, vehicle dynamics, traffic rules, and nearby road users.
A-star, Hybrid A-star, lattice planners, optimization, and Model Predictive Control may be used at different stages.
Obstacle avoidance considers vehicles, pedestrians, cyclists, barriers, debris, and construction zones.
Emergency braking provides an independent response when collision becomes critical.
Path Planning in Mobile Robots
Indoor mobile robots commonly use occupancy grids and graph-search algorithms.
A-star or Dijkstra’s algorithm calculates a global route.
Dynamic Window, Timed Elastic Band, or Vector Field Histogram methods manage local movement.
Cost maps represent walls, furniture, people, restricted areas, and obstacle inflation.
The robot continuously updates local obstacles using LiDAR, cameras, depth sensors, and ultrasonic sensors.
In crowded environments, human-aware cost maps and movement prediction improve social navigation.
Path Planning in Drones
Drone planning occurs in three-dimensional space.
The planner must consider buildings, terrain, trees, wires, airspace restrictions, wind, altitude limits, energy use, and emergency landing locations.
Grid-based, voxel-based, RRT, RRT-star, A-star, and optimization methods may be used.
The trajectory must remain dynamically feasible and maintain flight stability.
Local avoidance requires rapid three-dimensional sensing.
Thin objects such as wires remain particularly difficult because they may be weakly represented by sensors.
Path Planning in Robotic Manipulation
A robotic arm must move its joints without colliding with the environment, itself, or the object it is carrying.
Its configuration space may contain many dimensions.
Sampling-based methods such as Probabilistic Roadmaps and RRT are commonly used.
The planner considers joint limits, self-collision, obstacle collision, gripper orientation, and target pose.
Trajectory optimization smooths the movement and reduces time or energy.
When manipulating an object, the object becomes part of the robot’s effective geometry and must be included in collision checking.
Path Planning in Agriculture and Off-Road Systems
Agricultural robots navigate fields, crop rows, orchards, and uneven terrain.
Planning must consider field boundaries, crop protection, slope, soil condition, obstacles, coverage efficiency, and machine turning radius.
Coverage planning creates routes that allow the system to inspect, spray, plant, or harvest an entire area.
The shortest route may not be suitable if it repeatedly crosses crops or requires difficult turns.
Off-road planning may use elevation maps and terrain-cost models.
The system may avoid steep, muddy, unstable, or energy-intensive regions.
Coverage Path Planning
Coverage path planning determines how an autonomous system can visit or observe an entire region.
It is used in cleaning robots, agricultural spraying, lawn mowing, inspection, search missions, and mapping.
Back-and-forth patterns are common in rectangular areas.
More complex environments may be divided into smaller cells, with a coverage pattern generated inside each one.
The planner attempts to reduce missed areas, repeated coverage, turning, and travel time.
Dynamic obstacles may require temporarily skipping an area and returning later.
Coverage planning differs from ordinary point-to-point navigation because the objective is to cover a complete region rather than only reach one destination.
Ethical and Social Considerations
Path-planning decisions affect people sharing the environment.
A route that minimizes travel time may pass too close to pedestrians or create discomfort.
A delivery robot should not block accessibility ramps, doorways, or emergency routes.
An autonomous vehicle should not use aggressive manoeuvres simply because they reduce delay.
A drone should respect restricted airspace, privacy, and public safety.
Social and legal constraints should be represented as hard restrictions or strong planning costs.
Efficiency should not override human safety, accessibility, or lawful operation.
Cybersecurity
Path planning may be affected by manipulated maps, false obstacle data, GPS spoofing, communication attacks, or altered planner parameters.
A false map update may direct the autonomous system into a restricted or unsafe region.
An attacker may create artificial obstacles to block movement or remove real obstacles from digital representations.
The system should authenticate maps and software updates.
Independent sensors should verify external route information.
Safety monitors should reject paths that violate physical, geographic, or operational limits.
Decision and route logs should support later investigation.
Limitations
No single path-planning or obstacle-avoidance algorithm performs best in every situation.
Dijkstra’s and A-star provide reliable graph search but depend on map resolution and may produce angular paths.
Incremental methods improve replanning but still require accurate map updates.
Sampling-based methods handle high-dimensional spaces but may produce irregular paths and uncertain computation time.
Reactive methods respond quickly but may become trapped or ignore long-term route structure.
Optimization methods produce smooth trajectories but may converge to local solutions.
Learning-based methods adapt to complex environments but depend on training data and may fail unpredictably.
Dynamic obstacle avoidance depends on uncertain movement prediction.
Reliable autonomy therefore requires layered planning, sensor fusion, continuous monitoring, safety constraints, and fallback behaviour.
Conclusion
Path-planning algorithms determine how an autonomous system can move from its current position to a destination, while obstacle-avoidance algorithms protect it from immediate and future collisions.
Global planning uses large-scale map information to select a route. Local planning follows that route while reacting to nearby obstacles and environmental change.
Dijkstra’s algorithm finds the lowest-cost path but may explore large areas. A-star uses a heuristic to focus the search toward the destination. D-star, D-star Lite, and Lifelong Planning A-star support efficient replanning when map costs change.
Theta-star and Jump Point Search improve grid-based planning efficiency or path shape.
Visibility graphs, Voronoi diagrams, Probabilistic Roadmaps, RRT, RRT-star, and related sampling methods support planning in continuous and high-dimensional spaces.
Hybrid A-star, Dubins paths, Reeds–Shepp paths, and kinodynamic planners consider vehicle movement constraints.
Reactive obstacle-avoidance methods include Bug algorithms, Artificial Potential Fields, Vector Field Histograms, and Follow-the-Gap approaches.
The Dynamic Window Approach, Timed Elastic Band planning, trajectory rollout, velocity obstacles, and Model Predictive Control generate short-term feasible movement while considering speed, acceleration, and obstacle motion.
Cost maps, obstacle inflation, collision checking, braking distance, time to collision, uncertainty, and safety margins connect planning theory with physical operation.
Dynamic environments require object tracking, trajectory prediction, space–time planning, and continuous replanning.
Multi-robot environments additionally require coordination, reservation, priority, congestion management, and deadlock recovery.
The most reliable autonomous systems do not depend on one planning method. They combine global search, local avoidance, trajectory optimization, feedback control, learned prediction, and independent safety monitoring.
A successful path is not simply the shortest line between two points. It is a route that is physically feasible, dynamically safe, legally valid, understandable, and adaptable to changing real-world conditions.
Comments are closed.