Plans as Automata

Plans as Automata: strip away the agents and the LLMs and a plan is a transition system - states are sets of completed tasks, and each step completes one task whose dependencies are satisfied. Which means questions about plans ("can it finish?", "must it finish?", "what can run together?") aren't matters of testing or opinion: they're REACHABILITY, and small plans let us compute the entire state space and simply look.

source on github

a real captured run

PLANS AS AUTOMATA (the whole state space, enumerated)

  the diamond (a -> b,c -> d):
    reachable states: 6 (of 16 conceivable subsets)
    terminal states:  1 -> 1 complete, 0 stuck
    max choice: 2 tasks ready at once from one state

  the cycle (x <-> y):
    reachable states: 1 (of 4 conceivable subsets)
    terminal states:  1 -> 0 complete, 1 stuck
    STUCK at {} - no task can ever fire
    max choice: 0 tasks ready at once from one state

  what enumeration buys that testing cannot: the diamond's 6
  reachable states include EVERY execution order the scheduler
  could ever choose - both b-then-c and c-then-b paths converge,
  so completion isn't 'observed in CI', it's TOTAL: all runs
  reach {a,b,c,d}, by exhaustion of a 6-state space rather than
  by sampling it. the cycle tells the opposite story with the
  same rigor: its only terminal state is the empty set - not one
  task can EVER fire - which is why round 9's depth invariant
  had to excuse itself on cycles: there is no altitude in a
  building with no floors. plans are small automata; for small
  automata, don't argue about behavior - enumerate it. (at 40
  tasks the state space outgrows the universe; that's what the
  invariant provers are for. know which regime you're in.)

source

# frozen_string_literal: true

# Plans as Automata: strip away the agents and the LLMs and a plan is
# a transition system - states are sets of completed tasks, and each
# step completes one task whose dependencies are satisfied. Which
# means questions about plans ("can it finish?", "must it finish?",
# "what can run together?") aren't matters of testing or opinion:
# they're REACHABILITY, and small plans let us compute the entire
# state space and simply look.
#
#   bundle exec ruby examples/plans_as_automata.rb
#
# Runs offline; the whole state machine is enumerated, then judged.

require class="s">"bundler/setup"
require class="s">"agentic"
require class="s">"set"

def task_named(name)
  Agentic:class="y">:Task.new(description: name, agent_spec: {class="s">"name" => name, class="s">"instructions" => class="s">"w"})
end

def diamond
  o = Agentic:class="y">:PlanOrchestrator.new
  a, b, c, d = %w[a b c d].map { |n| task_named(n) }
  o.add_task(a)
  o.add_task(b, [a])
  o.add_task(c, [a])
  o.add_task(d, [b, c])
  o
end

def cyclic
  o = Agentic:class="y">:PlanOrchestrator.new
  x = task_named(class="s">"x")
  y = task_named(class="s">"y")
  o.add_task(x, [y.id])
  o.add_task(y, [x])
  o
end

# The operational semantics, in one method: from a state (set of done
# tasks), any task whose deps are all done may fire next
def steps(graph, done)
  graph[class="y">:tasks].keys.reject { |t| done.include?(t) }
    .select { |t| graph[class="y">:dependencies][t].all? { |d| done.include?(d) } }
end

# Enumerate the full transition system by breadth-first search
def state_space(graph)
  names = graph[class="y">:tasks].transform_values(&class="y">:description)
  initial = Set.new
  seen = {initial => []}
  frontier = [initial]
  until frontier.empty?
    state = frontier.shift
    steps(graph, state).each do |task|
      next_state = state | [task]
      unless seen.key?(next_state)
        seen[next_state] = []
        frontier << next_state
      end
      seen[state] << names[task]
    end
  end
  seen
end

def judge(title, orchestrator)
  graph = orchestrator.graph
  space = state_space(graph)
  all = graph[class="y">:tasks].keys.to_set
  final = space.keys.select { |s| steps(graph, s).empty? }
  complete = final.select { |s| s == all }
  stuck = final - complete

  puts class="s">"  #{title}:"
  puts class="s">"    reachable states: #{space.size} (of #{2**all.size} conceivable subsets)"
  puts class="s">"    terminal states:  #{final.size} -> #{complete.size} complete, #{stuck.size} stuck"
  if stuck.any?
    names = graph[class="y">:tasks].transform_values(&class="y">:description)
    stuck.each { |s| puts class="s">"    STUCK at {#{s.map { |t| names[t] }.sort.join(", class="s">")}} - no task can ever fire" }
  end
  widest = space.keys.max_by { |s| steps(graph, s).size }
  puts class="s">"    max choice: #{steps(graph, widest).size} tasks ready at once from one state"
  puts
  [space, complete, stuck]
end

puts class="s">"PLANS AS AUTOMATA (the whole state space, enumerated)"
puts
space, complete, = judge(class="s">"the diamond (a -> b,c -> d)", diamond)
_, complete2, stuck2 = judge(class="s">"the cycle (x <-> y)", cyclic)

puts class="s">"  what enumeration buys that testing cannot: the diamond's #{space.size}"
puts class="s">"  reachable states include EVERY execution order the scheduler"
puts class="s">"  could ever choose - both b-then-c and c-then-b paths converge,"
puts class="s">"  so completion isn't 'observed in CI', it's TOTAL: all runs"
puts class="s">"  reach {a,b,c,d}, by exhaustion of a 6-state space rather than"
puts class="s">"  by sampling it. the cycle tells the opposite story with the"
puts class="s">"  same rigor: its only terminal state is the empty set - not one"
puts class="s">"  task can EVER fire - which is why round 9's depth invariant"
puts class="s">"  had to excuse itself on cycles: there is no altitude in a"
puts class="s">"  building with no floors. plans are small automata; for small"
puts class="s">"  automata, don't argue about behavior - enumerate it. (at 40"
puts class="s">"  tasks the state space outgrows the universe; that's what the"
puts class="s">"  invariant provers are for. know which regime you're in.)"

exit((complete.any? && stuck2.any? && complete2.empty?) ? 0 : 1)