AI Glossary / Graphs and symbolic AI / Intermediate
Goal test
Definition
A goal test is a procedure that determines whether a candidate state satisfies the goal of a search or planning problem. In the usual classical setting, it returns true or false. It can compare the state with a specified target or evaluate a collection of conditions describing acceptable outcomes.
What it means
The goal states what success means; the goal test checks whether the represented situation meets that definition. For a puzzle, it might inspect tile positions. For a planning task, it might verify that several required predicates hold together.
The test is separate from the search strategy that chooses which candidate to inspect next. A correct test does not by itself make search efficient or guarantee the cheapest solution. Conversely, a sophisticated search method can still return an unsuitable result if the test leaves out an essential completion condition.
How it works
Define the state representation and translate each required goal condition into a check. Apply the test to the initial state and to candidate states at the points specified by the search algorithm. If a state passes, the algorithm can use its associated search node to recover the action path when appropriate.
Some goal tests recognize many acceptable states without listing them explicitly. The representation must contain enough information to evaluate the conditions. If success depends on the path taken, the relevant history must be tracked or handled by a suitable trajectory constraint; a location-only state cannot reveal whether a forbidden action occurred earlier.
Three practical examples
- A sliding-tile solver compares the current arrangement with its target configuration.
- A graph-coloring search checks that every vertex has an allowed color and every required adjacent pair differs.
- A simulated workflow checks that all mandatory stages have reached their required completion states before marking the task complete.
Think of it this way
Think of an acceptance checklist applied to a candidate result. Every mandatory item must pass before the result is accepted. The analogy is limited because classical goal tests operate on a formal state representation; they cannot inspect omitted facts or supply human judgment that was never encoded in the test.
Worked example
Represent a fictional task state as (location, sealed, receipt_recorded). The goal requires location = DeskB, sealed = true, and receipt_recorded = true.
State S1 = (DeskB, true, false) fails because the receipt is missing. State S2 = (DeskA, true, true) fails because the location is wrong. State S3 = (DeskB, true, true) passes. A faulty test that checks only location would incorrectly accept S1 and could accept an unsealed state as well.
Now suppose two valid paths reach S3. One costs 12 units and another costs 7. The goal test returns true for both because both satisfy the completion conditions. Finding which path is cheaper is the search algorithm's job, using the cost model. This separation is why detecting a goal on generation can be inappropriate for some cost-sensitive algorithms even though the goal test itself is correct.
Illustrative case study
In a fictional puzzle application, the Willow team marks a board solved whenever its displayed score reaches a threshold. An unusual board achieves the score while leaving two required positions wrong. The team replaces the proxy with a direct check of the puzzle's target conditions.
It tests valid solutions, partially solved boards, and the already-solved initial board. It also checks that reconstructing the returned path leads to the accepted state. This invented case demonstrates verification of the success predicate, not a measured improvement in a deployed solver.
Common misconceptions and mistakes
A heuristic estimate is not a goal test. A heuristic can assign zero to a non-goal state unless the heuristic's definition rules that out. Similarly, high confidence, a low loss, or lack of recent progress does not automatically mean the goal is satisfied.
Do not confuse “a goal was found” with “an optimal goal path was proved.” Do not assume that checking only the final state enforces all path constraints. If the initial state already satisfies the goal, a classical search problem may legitimately have an empty action sequence as its solution.
Business use
The concept supports reliable completion criteria in AI workflows. It encourages teams to define what evidence is needed before reporting success and to distinguish mandatory conditions from convenient proxies.
Review the test against examples that almost satisfy the request. Missing one required field, an incorrect object identifier, or an incomplete review state can expose a weak predicate. Where the system's state does not include the necessary information, improve the representation or add an explicit verification stage. A passing internal test is meaningful only within those modeled conditions.
People also ask
Can a goal test accept more than one state?
Yes. It can evaluate a condition shared by many acceptable states.
Does passing prove that the path is cheapest?
No. That requires the search algorithm and its assumptions to establish optimality.
Can the initial state pass?
Yes. In that case, no action may be needed for the formal task, although other operational requirements must still be represented if they matter.
Check your understanding
In the worked example, what should the test return for (DeskB, false, true)?
Answer: False. The location and receipt conditions hold, but the item is not sealed. The conjunction requires all three conditions, so two successful checks are insufficient.
Related terms
- Goal
- Search algorithm
- Heuristic function
- Terminal test
- goal state
- state representation
- path cost
- acceptance criterion
Learn next
Learn next about search-node selection and optimality. Draw a graph with a costly direct route to a goal and a cheaper two-edge route to the same goal. Keep the goal test unchanged and compare when breadth-first search and uniform-cost search are permitted to stop under their respective assumptions.
More in Graphs and symbolic AI
- Global maximum - A global maximum is the greatest value that an objective function actually attains anywhere in its specified feasible set.
- Global minimum - A global minimum is the smallest value an objective function actually reaches over its entire feasible set. A point that reaches it is a global minimizer.
- Goal clauses - Goal clauses are clauses with no positive literals, used in Horn-clause logic and resolution-based reasoning to represent goals to be proved by refutation.
- Goal-directed reasoning - Goal-directed reasoning organizes inference around a particular question or target conclusion.
- Goal formulation - Goal formulation is the process of deciding what an agent should try to achieve and expressing that outcome clearly enough to guide reasoning.
- Gomory-Hu Tree - A Gomory-Hu tree is a weighted tree that compactly represents the minimum cut values between every pair of vertices in an undirected capacitated graph.
Sources
Russell and Norvig, original Solving Problems by Searching chapter, problem components and goal tests: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf AIMA original breadth-first-search pseudocode: https://github.com/aimacode/aima-pseudocode/blob/master/md/Breadth-First-Search.md
Previous: Goal monitoring Next: Gödel machine