Is a reachable set a probability distribution?

No. It identifies possible states without necessarily assigning probabilities.

Must it be a continuous region?

No. Finite or countable state systems can have discrete reachable sets.

Are all states reachable if enough time is allowed?

Not necessarily. Transition restrictions, dynamics, and obstacles may permanently exclude states.

AI Glossary / Graphs and symbolic AI / Intermediate

Reachable set

Definition

A reachable set is the collection of states a system can attain from specified initial conditions under the allowed transitions or inputs. Its meaning depends on the model, constraints, and time horizon. States reachable at exactly a given time must be distinguished from states reachable at any time up to that limit.

What it means

A state describes the information needed to determine how the modeled system can evolve. For a simple workflow, it may be a status label. For a moving machine, it may include position and velocity. Reachability asks which states are possible, not which are most likely or most desirable.
The starting conditions are part of the question. A target can be reachable from one initial state but not another. Input restrictions also matter: adding a permitted action can expand the reachable set, whereas imposing an additional constraint can remove possibilities. These comparisons assume the rest of the model remains unchanged.

How it works

For a finite transition system, begin with the initial states and repeatedly apply every allowed outgoing transition. Keep the states reached at each step and, if required, their union across steps. Continue until the chosen horizon or until no new states appear.
Continuous systems need representations such as intervals, polytopes, or other regions rather than a list of every point. Computations often produce approximations. An outer approximation contains the true set; an inner approximation lies inside it. Whether a conclusion is valid depends on that direction, the model assumptions, and whether the calculation covers the required interval rather than only its final instant.

Three practical examples

A workflow designer can check whether an error status is attainable from an approved starting configuration under the modeled actions.
A robot-planning team can investigate which positions and velocities are attainable within a specified time and input budget.
A controller-verification exercise can compare a conservative reachable region with a forbidden region to assess a narrowly defined safety property.

Think of it this way

Think of marking every destination you could reach on a transport map within three transfers. That marked set says what is possible under the map's rules, not where you will actually travel. The analogy becomes limited when the system has continuous positions, uncertain dynamics, or constraints that apply throughout a journey.

Worked example

Consider an original discrete system with integer state x, initial state x0 = 0, and update x(next) = x + u. At every step, the permitted input is either −1 or +1; staying still is not allowed.
At exactly zero steps, R0 = {0}. At one step, R1 = {−1, 1}. At two steps, R2 = {−2, 0, 2}, because the four input sequences produce −2, 0, 0, and 2. At three steps, R3 = {−3, −1, 1, 3}.
The set reachable within three steps is the union R0 ∪ R1 ∪ R2 ∪ R3 = {−3, −2, −1, 0, 1, 2, 3}. State 2 is reachable within three steps but not at exactly three steps. This difference arises because every move changes parity and waiting is unavailable.
Now require every visited state to remain nonnegative. The exact three-step set becomes {1, 3}: trajectories that cross below zero are forbidden. Checking only a final state would miss such violations; the sequence −1, +1, +1 ends at 1 but violates the constraint on its first step.
Finally, the continuous interval [−3, 3] is an outer approximation of the unconstrained exact-three-step set. It includes 2 even though 2 is not attainable at that step. Membership in an outer approximation alone therefore does not establish actual reachability.

Illustrative case study

In a fictional case, Fern Automation models a job-processing workflow before deploying a new routing rule. The initial status is “received,” and edges represent permitted status changes. Engineers ask whether a job can reach “published” without passing through “reviewed.”
A discovered path provides a concrete sequence to inspect. If their exhaustive finite-state analysis finds no such path, the conclusion applies to the encoded transition rules and initial conditions. The team still checks that the application implements those rules and that omitted states do not invalidate the model. This is an illustrative review process, not a reported product outcome.

Common misconceptions and mistakes

A reachable state need not be probable, safe, or desirable. Failure to find it in a handful of simulations does not prove it unreachable. Conversely, its presence in a conservative outer approximation does not prove that an actual trajectory reaches it.
Endpoint reachability does not automatically establish safety along the entire path. In uncertain control problems, “some allowed input can reach the target” differs from “a controller can guarantee reaching it despite every allowed disturbance.” State clearly which quantifiers and constraints the analysis uses.

Business use

Reachability helps teams turn broad claims into specific questions: can this workflow enter a prohibited status, can this mechanism attain a target before the deadline, or can modeled disturbances carry a controller into a forbidden region?
Record initial conditions, input limits, horizon, model version, and approximation direction. For an outer approximation, no intersection with the forbidden set can support exclusion under the model. An intersection usually calls for refinement or a concrete trajectory; it may reflect approximation looseness rather than an actual failure.

Check your understanding

Why is 2 absent from the exact-three-step set in the example?

Answer: Starting at 0, three moves of ±1 always produce an odd integer. It is nevertheless reachable in two steps.

Related terms

State space
Controllability
Model checking
transition system
reachability analysis
forward reachable set
backward reachable set
overapproximation

Learn next

Add the input u = 0. At exactly three steps, every integer from −3 through 3 becomes reachable, because shorter sequences can be padded with waiting. Explain how this single change removes the example's parity restriction.

Sources

Sources: LaValle, Planning Algorithms, reachable sets and time-limited reachability: https://msl.cs.uiuc.edu/planning/node731.html and https://msl.cs.uiuc.edu/planning/node732.html . MIT OpenCourseWare, Cognitive Robotics, Advanced Lecture 5 transcript: https://ocw.mit.edu/courses/16-412j-cognitive-robotics-spring-2016/3745f624ffefcafe45775742a24c44f8_qgL0cA7GkJo.pdf . Tedrake, Underactuated Robotics, finite-time reachability and approximation direction: https://underactuated.csail.mit.edu/lyapunov.html .

Previous: Re-ranking Next: Reactive control