Package com.tnsai.planning

Class BackwardChainingPlanner

java.lang.Object
com.tnsai.planning.BackwardChainingPlanner
All Implemented Interfaces:
Planner
public class BackwardChainingPlanner extends Object implements Planner
Default planner implementation using backward chaining algorithm.

Backward chaining starts from the goal and works backwards to find a sequence of actions that can achieve it. This is effective when:

  • The goal is well-defined
  • Actions have clear preconditions and effects
  • Multi-step plans are needed

Algorithm

 function plan(goal, state):
     if goal is satisfied in state:
         return empty plan

     for each action that fulfills goal:
         if action's precondition is satisfied:
             return [action]
         else:
             subplan = plan(precondition, state)
             if subplan exists:
                 return subplan + [action]

     return no plan found

Active recursion is guarded by the target precondition and a snapshot of simulated state, so revisiting an action after the state has moved on is still valid while a genuine loop is not.

An empty plan means one thing: every goal was already satisfied. Anything else raises PlanningFailureException, whose reason tells an unreachable goal apart from a cyclic precondition, an exhausted depth budget, and an exhausted search budget.

Usage


 Planner planner = new BackwardChainingPlanner(MyRole.class);
 Map<String, Object> state = Map.of("health", 30, "ammo", 5);
 List<PlanningAction> plan = planner.plan(state);
Author:
TnsAI Team
See Also:

  • Constructor Details

    • BackwardChainingPlanner

      public BackwardChainingPlanner(Class<?> roleClass)
      Creates a planner from a role class.

      Extracts goals from @RoleSpec and actions from @Action methods.

      Parameters:
      roleClass - class annotated with @RoleSpec

    • BackwardChainingPlanner

      public BackwardChainingPlanner(Class<?> roleClass, int maxDepth)
      Creates a planner from a role class with custom max depth.
      Parameters:
      roleClass - class annotated with @RoleSpec
      maxDepth - requested maximum planning depth; values above the internal recursion safety ceiling are capped

    • BackwardChainingPlanner

      public BackwardChainingPlanner(List<PlanningGoal> goals, List<PlanningAction> actions)
      Creates a planner with explicit goals and actions.
      Parameters:
      goals - planning goals
      actions - available actions

    • BackwardChainingPlanner

      public BackwardChainingPlanner(List<PlanningGoal> goals, List<PlanningAction> actions, int maxDepth)
      Creates a planner with explicit goals, actions, and max depth.
      Parameters:
      goals - planning goals
      actions - available actions
      maxDepth - requested maximum planning depth; values above the internal recursion safety ceiling are capped

  • Method Details

    • plan

      public List<PlanningAction> plan(Map<String,Object> state)
      Description copied from interface: Planner
      Creates a plan to achieve unsatisfied goals.
      Specified by:
      plan in interface Planner
      Parameters:
      state - current state (belief map)
      Returns:
      ordered list of actions to execute; empty only when every registered goal is already satisfied

    • plan

      public List<PlanningAction> plan(Map<String,Object> state, boolean useChaining)
      Description copied from interface: Planner
      Creates a plan with optional chaining.
      Specified by:
      plan in interface Planner
      Parameters:
      state - current state
      useChaining - true to use backward chaining for multi-step plans
      Returns:
      ordered list of actions

    • maxDepth

      public int maxDepth()
      Configured recursion budget. Goal and precondition search both stop when remaining depth reaches zero.

    • planForGoalWithChaining

      public List<PlanningAction> planForGoalWithChaining(PlanningGoal goal, Map<String,Object> state, int maxDepth)
      Plans for a single goal using backward chaining.
      Parameters:
      goal - target goal
      state - current state
      maxDepth - requested recursion depth; values above the internal recursion safety ceiling are capped
      Returns:
      action sequence to achieve goal
      Throws:
      PlanningFailureException - when a cyclic precondition is detected, recursion depth is exhausted, or the bounded search budget is exhausted

    • getGoals

      public List<PlanningGoal> getGoals()
      Description copied from interface: Planner
      Returns all registered goals.
      Specified by:
      getGoals in interface Planner
      Returns:
      list of goals

    • getActions

      public List<PlanningAction> getActions()
      Description copied from interface: Planner
      Returns all registered actions.
      Specified by:
      getActions in interface Planner
      Returns:
      list of actions

    • findUnsatisfiedGoals

      public List<PlanningGoal> findUnsatisfiedGoals(Map<String,Object> state)
      Description copied from interface: Planner
      Finds goals that are not currently satisfied.
      Specified by:
      findUnsatisfiedGoals in interface Planner
      Parameters:
      state - current state
      Returns:
      unsatisfied goals, ordered by priority (highest first)

    • findSatisfiedGoals

      public List<PlanningGoal> findSatisfiedGoals(Map<String,Object> state)
      Description copied from interface: Planner
      Finds goals that are currently satisfied.
      Specified by:
      findSatisfiedGoals in interface Planner
      Parameters:
      state - current state
      Returns:
      satisfied goals

    • isGoalSatisfied

      public boolean isGoalSatisfied(String goalName, Map<String,Object> state)
      Description copied from interface: Planner
      Checks if a specific goal is satisfied.
      Specified by:
      isGoalSatisfied in interface Planner
      Parameters:
      goalName - goal name
      state - current state
      Returns:
      true if goal condition is satisfied

    • findActionsForGoal

      public List<PlanningAction> findActionsForGoal(PlanningGoal goal, Map<String,Object> state)
      Description copied from interface: Planner
      Finds actions that can help achieve a goal.
      Specified by:
      findActionsForGoal in interface Planner
      Parameters:
      goal - target goal
      state - current state
      Returns:
      applicable actions for the goal

    • findApplicableActions

      public List<PlanningAction> findApplicableActions(Map<String,Object> state)
      Description copied from interface: Planner
      Finds actions whose preconditions are satisfied.
      Specified by:
      findApplicableActions in interface Planner
      Parameters:
      state - current state
      Returns:
      applicable actions

    • applyEffects

      public Map<String,Object> applyEffects(PlanningAction action, Map<String,Object> state)
      Description copied from interface: Planner
      Simulates applying an action's effects to a state.
      Specified by:
      applyEffects in interface Planner
      Parameters:
      action - action to apply
      state - state to modify (returns new state)
      Returns:
      new state after applying effects

    • extractState

      public static Map<String,Object> extractState(Object roleInstance)
      Extracts current state from @State annotated fields, including fields inherited from superclasses, which core's RoleSpecExtractor also collects. A subclass @State with the same name as an inherited one wins here.
      Parameters:
      roleInstance - role object instance
      Returns:
      state map