AI Glossary / Computer vision and multimodal AI / Beginner
Path finding
Definition
Path finding is the process of finding a sequence of valid connections from a starting state to a destination. Depending on the problem, the aim may be any feasible route or a route that minimizes a defined cost, such as distance, time or energy.
What it means
A path is more than a straight line drawn toward a goal. Walls, one-way links, unavailable actions and different travel costs determine which routes are possible and desirable. Many systems represent the problem as a graph: nodes describe locations or states, and edges describe allowed transitions. A node can include orientation or another relevant condition, rather than position alone. The best route therefore depends on the representation and objective. A route that minimizes walking distance may differ from one that minimizes travel time, avoids stairs or accommodates a robot's turning radius.
How it works
The system builds or receives a representation of valid connections and searches through it. Breadth-first search can find a path with the fewest edges when edges have equal cost. Dijkstra's algorithm handles nonnegative edge costs. A* uses both the cost accumulated so far and a heuristic estimate of the remaining cost to guide exploration.
Optimality depends on the algorithm, heuristic and implementation assumptions. For example, an admissible heuristic never overestimates the true remaining cost; graph-search implementations must also handle revisiting states correctly. Once the destination is reached, stored predecessor links reconstruct the route. Real systems may need to replan when obstacles, costs or the destination change. Following that route is a separate control task.
Three practical examples
- A warehouse simulation finds a route through aisles while respecting blocked passages.
- A game character navigates around walls using a graph or navigation mesh.
- A visual inspection tool searches for a low-cost connected path through an image, where edge costs represent evidence for a boundary.
Think of it this way
Think of planning a journey through connected rooms. You can only pass through existing doors, and each door can carry a time cost. Searching the room connections helps choose a route. The analogy becomes incomplete when the state must also represent timing, vehicle orientation or several moving agents; those details require a richer model than a simple floor plan.
Worked example
Suppose a graph offers two routes from S to G. Route S - A - G has edge costs 2 and 8, for a total of 10. Route S - B - C - G has costs 3, 2 and 2, for a total of 7. If cost is travel time, the second route is preferable even though it has more edges.
Breadth-first search would favor the two-edge route when treating all edges equally. Dijkstra's algorithm can find the cost-7 route using the stated nonnegative weights. If a new blockage removes B - C, that route is no longer valid. The earlier answer was optimal for the earlier graph, not a permanent guarantee about the environment.
Illustrative case study
In a fictional distribution-center simulation, a team initially minimizes the number of aisle segments between two stations. The simulated route repeatedly crosses a slow loading area. The team changes the edge weights to estimated travel times and compares the resulting routes against several representative layouts. The new objective reflects the operational question more closely. Before using the approach with physical equipment, the team separately considers clearance, localization, obstacle updates and movement control. This case illustrates a modeling choice; it does not claim measured productivity or safety results.
Common misconceptions and mistakes
A path with fewer steps is not necessarily faster or shorter in physical distance. A mathematically optimal route is only optimal for its specified graph and costs. A* does not automatically guarantee the best route under every heuristic or implementation. Straightening a path after search can create invalid shortcuts if obstacle clearance is not checked. Path finding is also not the same as discovering obstacles from camera images. Perception supplies information about the environment, while planning uses a representation of that information to choose actions.
Business use
Businesses can use path finding in logistics simulations, interactive products and robotic systems, but should first define what the route optimizes. Evaluate feasibility, cost, computation time and behavior when no route exists. Test narrow passages, disconnected regions and changing restrictions. For deployed movement systems, account for the age and uncertainty of the map. A clear explanation of why a route was selected can be more useful to an operator than presenting an unexplained line as the only possible answer.
People also ask
Does path finding require AI training?
No. Classical graph-search algorithms can find routes without learning from examples.
Can the shortest route change?
Yes. Changes to connections, costs, start state or destination can change the answer.
What happens when no route exists?
The system should report that the destination is unreachable under the current model, rather than inventing a connection or silently ignoring restrictions.
Check your understanding
One route has two edges costing 5 each. Another has four edges costing 1 each. Which is better when the objective is minimum total cost?
Answer: The four-edge route, with total cost 4, is better than the two-edge route costing 10. Edge count and total cost are different objectives.
Related terms
- Graph
- Shortest Paths
- Breadth First Search
- Dijkstra's algorithm
- Heuristic
- Motion planning
- shortest path
- A* search
- navigation mesh
- replanning
Learn next
Learn graph representations and weighted edges next. Then compare breadth-first search with Dijkstra's algorithm on a small map containing a slow area. Add A* only after explaining what its heuristic estimates and why that estimate is appropriate.
More in Computer vision and multimodal AI
- P-frame - A P-frame, or predictive frame, is a coded video picture that can use previously decoded reference pictures to predict image content.
- Panorama - A panorama is an image showing an extended view of a scene, often created by combining overlapping photographs into one continuous composition.
- Parallel projection - Parallel projection maps three-dimensional points onto a two-dimensional plane along parallel projection lines.
- Pattern grammar - A pattern grammar is a set of rules describing how simpler components can combine into structured patterns.
- PDE / diffusion inpainting (BertalmÃo) - PDE-based inpainting fills a selected missing or damaged image region using equations that propagate information from its surroundings.
- Peak signal-to-noise ratio (PSNR) - Peak signal-to-noise ratio, or PSNR, is a logarithmic measure comparing the allowed peak signal range with the mean squared error between a test image and a...
Sources
Red Blob Games, author's implementation guide to graph search and path reconstruction: https://www.redblobgames.com/pathfinding/a-star/implementation.html Red Blob Games, introduction to A* and related searches: https://www.redblobgames.com/pathfinding/a-star/introduction.html Primary-source search excerpts consulted; full source and editorial review remain pending.
Previous: Path consistency learning Next: Path planning