Is an and - or tree a decision tree classifier?

No. Here it represents problem-solving structure, not a learned classification rule.

Can it represent uncertainty?

It can represent possible outcomes, but probabilities require additional information.

Why use a graph instead of a tree?

Shared subproblems and repeated states can be represented once instead of copied.

AI Glossary / AI and machine learning / Intermediate

And - or tree

Definition

An and - or tree represents a problem using two kinds of branching. At an OR node, one suitable alternative can be enough; at an AND node, all required subproblems or possible outcomes must be addressed. The meaning depends on the planning or reasoning task being represented.

What it means

Many plans contain both choices and obligations. You may choose one of several delivery methods, but a chosen method may require several arrangements. A normal list of steps can conceal this structure.

And - or trees make the difference visible. An OR branch represents alternatives available to the planner. An AND branch may represent subgoals that must all be achieved. In planning with nondeterministic actions, it can instead represent several outcomes for which the plan must be prepared.

For a business reader, this is a practical distinction between choosing a route and covering everything the route requires. Finding one successful sequence is not enough when an action may produce different outcomes that the system cannot choose.

How it works

Start with the overall problem at the root. Decompose it into alternative solutions or jointly required parts. Continue until the leaves are solved tasks, achievable goals or recognized failures.

An OR node is solved when at least one child supplies a valid solution. An AND node is solved only when every required child is covered under the chosen interpretation. Search algorithms use these relationships to build a solution structure rather than merely a single path.

In a nondeterministic setting, choosing an action can lead to several possible states. A conditional plan specifies what to do after observing which state occurred. Cycles and repeated states require careful handling; practical planners often use graphs rather than duplicating every occurrence in a tree. Costs also need explicit rules because parallel prerequisites and alternative outcomes are not always added in the same way.

Three practical examples

A maintenance planner chooses between repair and replacement, then expands the prerequisites for the selected option.
A service agent prepares different responses for success and failure of an external booking request.
A diagnostic system represents alternative explanations while tracking the evidence required to establish each one.

Think of it this way

Think of organizing a picnic. You can choose a park or an indoor venue, but using the park may require both transport and permission. A weather-dependent plan also needs a response if conditions change.

The analogy is limited because a formal planner needs exact states and success rules. A casual diagram can omit interactions, such as two tasks competing for the same resource.

Worked example

Checking whether a plan covers its branches

A fictional booking agent can choose Service A or Service B. Service A has two possible results: confirmed or unavailable. If confirmed, the goal is reached. If unavailable, the agent must try a supported fallback or report that no booking was made.

The choice between services is an OR decision: the agent selects one. The results of the chosen service form an AND requirement for a robust conditional plan: every represented outcome needs an appropriate continuation.

A diagram containing only “choose A → confirmed” shows one favorable path, not complete coverage. Adding “unavailable → choose B” helps only if B's possible results are also handled. This example concerns plan completeness, not probabilities; it makes no assumption that success and failure are equally likely. A failure report completes a reporting workflow only if that is an allowed goal. If the goal is strictly to obtain a booking, reporting failure does not make that branch a solution.

Illustrative case study

A fictional equipment-rental company automates reservation checks. Its original workflow assumes that a requested item remains available between search and confirmation. Occasionally another booking takes the item first, leaving the customer without a clear result.

The team represents confirmation outcomes explicitly and gives each a continuation: confirmed bookings proceed, unavailable items trigger alternatives, and ambiguous responses trigger a status check. It tests the actual service responses against the model.

The lesson is that a useful plan includes more than its happy path. The and - or structure helps reveal the missing continuation but does not itself make external services reliable.

Common misconceptions and mistakes

AND always means steps execute simultaneously. It means all relevant branches are required; timing depends on the model.
OR means every alternative is tried. One valid alternative may suffice.
A successful path proves a nondeterministic plan is complete. Other possible outcomes may still lack a solution.

Business use

And - or reasoning helps teams design workflows with alternatives, prerequisites and contingencies. It is useful before implementation because a missing branch can be discussed in business terms rather than discovered as an unexplained software failure.

Keep diagrams small enough to review and state what each branch means. If the process includes shared resources, repeated attempts or partial information, the technical model may need more than a simple tree. The diagram should clarify the problem rather than disguise that complexity.

Check your understanding

A planner can choose one supplier, but the chosen supplier may accept or reject the order. Which part is OR and which needs AND-style coverage?

Answer: Supplier choice is OR. A conditional plan must cover each represented supplier response.

Related terms

Search tree
Conditional plan
State space
planning
nondeterminism
goal decomposition
AO* search

Learn next

Read conditional planning and state space. Draw a familiar workflow using separate symbols for choices and outcomes that all need handling, then inspect any uncovered branch.

State space

Sources

Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Search with Nondeterministic Actions: https://aima.cs.berkeley.edu/errata/aima-125.pdf. Author-provided material describes and–or search and conditional plans. The booking and rental examples are original teaching scenarios.

Previous: And-Elimination Next: AND-parallelism