Course contentsShow
← Computer Science
Lesson 2732 of 2,87261. AI and Search AlgorithmsFree lesson

Action Space and Successor Functions

Defining valid actions from each state and implementing functions that generate successor states.

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:

  1. What actions are legal right now? (action space)
  2. 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.