Action Space and Successor Functions
You'll learn: How to define what moves are legal from any state and how to systematically generate the resulting next states in search problems.
The Core Idea
In AI search, once you've defined your state space, you need to answer two critical questions for every state: "What can I do from here?" and "Where will each action take me?" The action space is the set of all valid actions available from a given state, and a successor function takes a state and an action to produce the resulting new state.
Think of it like a video game: at any moment (state), you have certain moves available (action space), and pressing a button (applying an action) updates the game to a new configuration (successor state).
Why This Matters
Not all actions are valid in every state. In a chess game, you can't move a pawn backward. In route planning, you can't drive down a one-way street the wrong way. Your search algorithm needs to know:
- What actions are legal right now? (action space)
- What state results from taking action A? (successor function)
The successor function is often written as:
successor(state, action) → new_state
Or you might see a function that returns all possible next states:
get_successors(state) → list of (action, new_state, cost) tuples
Practical Design
When implementing search algorithms, you typically define these functions based on your domain rules. The action space might be a fixed set (['UP', 'DOWN', 'LEFT', 'RIGHT']) with validity checks, or it might be dynamically generated based on the current state's constraints.
Key Takeaway: The action space defines valid moves from each state, and successor functions compute resulting states—together they form the bridge between abstract states and concrete transitions in your search problem.