Is the frontier the same as the explored set?

No. The explored set usually records states already expanded, while frontier candidates await expansion.

Must the frontier be sorted?

No. Queues and stacks need no full cost ordering. Priority-based algorithms maintain the ordering they require.

Can a frontier contain two records for one state?

Some implementations allow this and discard stale records later. Others update a single active entry. Correctness depends on the surrounding bookkeeping.

AI Glossary / Graphs and symbolic AI / Beginner

Frontier

Definition

A frontier is the collection of search nodes that have been discovered and are waiting to be selected for further exploration. It represents the boundary between the search work already performed and the candidate paths still available to pursue.

What it means

A search algorithm begins with a starting point and discovers possible next steps. It usually cannot explore every possibility at once, so it stores candidates in a frontier, also called an open list or fringe.

The frontier is not the entire search space. Undiscovered states are not yet in it, and states already expanded may be stored separately. A search node can also contain more than a state: it may record a parent, an action and the path cost used to reach that state.

This entry uses the algorithmic search meaning. It does not refer to frontier AI models or to a geographical boundary, although the everyday image of an advancing boundary can be helpful.

How it works

The algorithm places its initial node on the frontier. It selects a node according to its search policy, examines or expands it, and adds eligible successors. Goal testing and duplicate handling follow the algorithm's specified rules.

The frontier's ordering determines much of the search behavior. Breadth-first search typically uses a first-in, first-out queue. Depth-first search typically uses a stack. Uniform-cost search prefers the smallest path cost, while A* uses a priority based on path cost plus a heuristic estimate.

Graph search must also manage repeated states. It may replace an existing frontier record when a cheaper path is found, or insert a new record and later ignore an obsolete one. The physical data structure and the logical set of active candidates therefore need not be identical.

Three practical examples

Route finding: Candidate locations and their path information wait in a priority queue until the planner explores them.
Puzzle solving: The frontier holds board configurations reached by possible move sequences but not yet expanded.
Workflow planning: Alternative partial plans remain available while the system chooses which one to develop next.

Think of it this way

Think of a researcher's tray of promising leads awaiting investigation. A lead enters the tray when discovered and leaves when investigated or discarded under a rule. The analogy highlights pending work. A formal search algorithm also requires precise state identity, ordering and correctness conditions that an informal tray does not provide.

Worked example

Consider a graph with start S. S has successors A and B; A has successor C; B has successors C and D. Assume an unweighted breadth-first graph search that marks states as reached when they enter the frontier and examines successors in the displayed order.

Initially, the frontier is [S]. Expand S and append its successors: [A, B]. Expand A and append C: [B, C]. Expand B next. C is already reached, so do not add a duplicate; append D instead: [C, D].

The frontier now contains two pending nodes, while S, A and B have already been expanded. C was discovered through A, and the later route through B does not create another active C entry under this policy.

If the same graph used a stack and successors were pushed A then B, B would be selected before A. The graph has not changed, but the frontier policy changes the exploration order.

For weighted search, ignoring every later route merely because a state was reached can be wrong. Suppose C was first reached at cost 10 and later at cost 4. A cost-sensitive algorithm may need to update or reopen its record. The duplicate rule must match the search algorithm's guarantees.

Illustrative case study

Fictional case: Maple Planner displays the number of pending routes during a simulation. Its dashboard labels every reached state as “frontier,” including states already expanded.

The team corrects the display to distinguish active candidates, expanded states and newly generated successors. A second review finds that the priority queue can contain obsolete entries after a cheaper route is discovered, so the raw queue length is not always the number of distinct active states.

The team defines both measures and checks the parent links used to reconstruct the returned route. The case illustrates why a seemingly simple progress count depends on the implementation's precise frontier and duplicate-management conventions.

Common misconceptions and mistakes

The frontier contains every possible future state. It contains discovered candidates, not all undiscovered possibilities.
A state and a search node are always interchangeable. Different nodes can represent different paths to the same state.
The first discovered route is always best. That depends on the search method and edge-cost assumptions.
An empty frontier always proves the original problem impossible. That conclusion requires a complete search over the relevant finite or otherwise supported problem; pruning or resource limits can change what was explored.

Business use

Understanding the frontier helps teams diagnose search memory use, latency and progress. A rapidly growing frontier can indicate a broad search space, weak guidance or duplicate-management problems.

Define whether reported counts refer to nodes, distinct states or active queue records. Measure the memory needed for path and parent information as well as the frontier container itself. When changing queue policies for speed, verify that the search still meets its required completeness and solution-quality properties. The container choice is part of the algorithm's behavior, not merely a cosmetic implementation detail.

Check your understanding

After expanding S, a breadth-first search has frontier [A, B]. Expanding A discovers C, which has not been reached before. What is the next frontier?

Answer: [B, C], under a first-in, first-out queue and the stated successor order.

Related terms

State space
Breadth First Search
Depth First Search
Priority queue
Search node
open list
explored set
duplicate detection

Learn next

Continue the worked breadth-first trace until the frontier is empty. Then repeat it using a stack and record the expansion order. Finally, add a weighted alternative path and explain why the duplicate policy may need to change.

Sources

The AIMA search implementation shows frontier policies and graph-search bookkeeping: https://aimacode.github.io/aima-python/_modules/aima/search.html

The AIMA Java search framework describes frontier-based expansion and queue strategies: https://github.com/aimacode/aima-java/wiki/AIMA3e-Search-Framework

The graph trace and Maple Planner case are original illustrations. Count definitions and implementation alternatives are stated explicitly to avoid equating every physical queue record with a distinct active state.

Previous: Front-to-front Next: Full functional dependency