Definition
An And–or tree is a representation used in problem-solving and planning, particularly in AI search algorithms. ‘Or’ nodes represent choices between different actions, while ‘And’ nodes indicate that all subsequent sub-nodes must be satisfied to achieve a goal. This structure helps decompose complex problems into manageable subproblems, facilitating efficient search strategies like AO* for finding optimal solutions in non-deterministic environments.
Summary
A hierarchical graph structure used in search algorithms where nodes represent states and edges represent actions leading to subgoals.
Key Concepts
- Search algorithms
- Problem decomposition
- AO* algorithm
- State space
Use Cases
- Automated planning
- Game tree search
- Complex problem solving