AI

Hierarchical Task Network Planner

Hard
Agents

Implement Hierarchical Task Network (HTN) planner:

HTN Concepts:

  • Primitive tasks: Atomic actions (like operators in classical planning)
  • Compound tasks: Abstract, need decomposition
  • Methods: How to decompose compound tasks into subtasks

Methods:

  1. add_primitive(name, preconds, effects, cost): Define atomic action
  2. add_compound(name): Define abstract task
  3. add_method(compound, subtasks, preconds): Define decomposition
    • Multiple methods per compound = alternatives
  4. plan(goal, initial_state): Generate plan
    • Decompose compound tasks
    • Order primitive tasks
    • Return executable plan

State: Dict representing world state

Preconds/Effects: Dicts like {'has': 'key'} for preconditions, {'has': 'door_open'} for effects

Examples

Example 1:
Input: planner = HTNPlanner(); planner.add_primitive('move', {'at': 'A'}, {'at': 'B'}, 1); 'move' in planner.primitive_tasks
Output: True
Explanation: Primitive task added successfully

Starter Code

class HTNPlanner:
    """
    Hierarchical Task Network planner for complex goal achievement.
    """
    
    def __init__(self):
        self.primitive_tasks = {}  # Atomic actions
        self.compound_tasks = {}   # Decomposable tasks
        self.methods = {}          # Decomposition methods
    
    def add_primitive(self, name, preconds, effects, cost=1):
        """Add primitive (atomic) task"""
        # Your implementation here
        pass
    
    def add_compound(self, name):
        """Add compound (decomposable) task"""
        # Your implementation here
        pass
    
    def add_method(self, compound_name, subtasks, preconds=None):
        """
        Add method to decompose compound task.
        Multiple methods = alternative decompositions.
        """
        # Your implementation here
        pass
    
    def plan(self, goal, initial_state):
        """
        Generate plan to achieve goal from initial state.
        Returns plan (list of primitive tasks) or None.
        """
        # Your implementation here
        pass
    
    def is_applicable(self, task, state):
        """Check if task preconditions satisfied in state"""
        # Your implementation here
        pass
    
    def apply_task(self, task, state):
        """Apply task effects to state"""
        # Your implementation here
        pass
Lines: 1Characters: 0
Ready
The AI Interview - Master AI/ML Interviews