Skip to content

adityakulthe/sh

BranchesTags

Repository files navigation

SH Planning System

SH is a software system designed to solve complex planning problems in various domains. It is based on state-based Hierarchical Task Network (HTN) planning and supports multiple planning languages for specifying planning problems. What sets SH apart is its modular and service-oriented architecture, providing flexibility, extensibility, and maintainability. The SH planning system offers versatile capabilities, including modular parsing of planning problems, quick variable binding and predicate grounding on the fly during plan generation, resource-efficient plan generation, and seamless integration into other larger systems. These capabilities make SH suitable for addressing real-world challenges in planning, automation, assistance, and decision-making.

Features

  • Multi-Language Support: Parse and solve planning problems written in HPDL, HDDL, or SHOP2
  • Unified Internal Representation: All languages convert to a common intermediate representation
  • Modular Parser Architecture: Extensible design for adding new planning languages
  • HTN Optimization Framework: 9-stage optimization pipeline for enhanced planning efficiency
  • Service-Oriented: Available as a library or web service
  • Resource-Efficient: Optimized plan generation with on-the-fly variable binding
  • Comprehensive Domain Library: 8 benchmark domains with examples in all three languages
  • Validated Optimizations: Proven 75% dead branch removal and 37.5% search space reduction

Supported Planning Languages

HPDL (Hierarchical Planning Definition Language)

The native language of SH, based on PDDL with HTN extensions.

Example:

(define (domain basic)
  (:requirements :typing :hierarchy)
  (:types thing)
  (:predicates (p ?x - thing) (q ?x - thing))
  
  (:task do-something :parameters (?x - thing))
  
  (:method m-do-something
    :parameters (?x - thing)
    :task (do-something ?x)
    :precondition (p ?x)
    :subtasks (and
      (make-q ?x)))
  
  (:action make-q
    :parameters (?x - thing)
    :precondition (p ?x)
    :effect (q ?x)))

HDDL (Hierarchical Domain Definition Language)

A standardized HTN planning language with support for both inline and separate method definitions.

Example:

(define (domain basic)
  (:requirements :typing :method-preconditions)
  (:types thing)
  (:predicates (p ?x - thing) (q ?x - thing))
  
  (:task do-something :parameters (?x - thing))
  
  (:method m-do-something
    :parameters (?x - thing)
    :task (do-something ?x)
    :precondition (p ?x)
    :ordered-subtasks (and
      (make-q ?x)))
  
  (:action make-q
    :parameters (?x - thing)
    :precondition (p ?x)
    :effect (q ?x)))

SHOP2 (Simple Hierarchical Ordered Planner 2)

A classic HTN planning language with Lisp-style syntax.

Example:

(defdomain basic (
  (:operator (!make-q ?x)
    ((p ?x))
    ()
    ((q ?x)))
  
  (:method (do-something ?x)
    ((p ?x))
    ((!make-q ?x)))))

Getting Started

Prerequisites

  • JDK 1.8 or higher
  • Scala 2.11.12
  • sbt (Scala Build Tool)
  • Dependencies specified in build.sbt

Installation

  1. Clone the repository:
git clone https://github.com/PlanX-Universe/sh.git
cd sh
  1. Build the project:
sbt compile
  1. Run tests:
sbt test

Usage

Using the Client Object

To run a planning problem, use the PlanningServices.planWithGivenDomainAndProblemNamePrintPlans service within the Client object:

PlanningServices.planWithGivenDomainAndProblemNamePrintPlans(
  domainName = "deployment",
  problemName = "p-dashboard",
  numberOfPlans = 1
)

Parameters:

  1. domainName: Name of the domain (matches directory in resources/repository/)
  2. problemName: Name of the problem file (without extension)
  3. numberOfPlans: Number of plans to generate (default: 1)

The system automatically detects the planning language based on file extension:

  • .hpdl → HPDL parser
  • .hddl → HDDL parser
  • .shop2 → SHOP2 parser

Running from Command Line

sbt run

Then modify the Client.scala file to specify your domain and problem.

Example Output

Plan 1:
1) createinstance(dashboard)
2) createinstance(apache2)
3) start(1.0)
4) bind(httpd,0.0,1.0)
5) start(0.0)
6) createinstance(cassandra)
7) start(2.0)
8) run(2.0)
9) bind(cass-up,0.0,2.0)
10) run(0.0)

-------------------------------------------* Statistics *-------------------------------------------
Number of found plans: 1
First plan length: 10
*************************************************
Parsing time: 968.0 ms
Plan-generation time: 63.0 ms
Memory usage: 133.169152 MB
*************************************************
Number of evaluated states: 34
Number of decomposed tasks: 24
Number of recursions: 36
----------------------------------------------------------------------------------------------------

Available Domains

The system includes 8 benchmark domains, each available in all three planning languages:

Domain Description HPDL HDDL SHOP2
basic Simple domain for testing ✅ ✅ ✅
blocksworld Classic blocks stacking problem ✅ ✅ ✅
cafeteria Restaurant service planning ✅ ✅ ✅
deployment Software deployment planning ✅ ✅ ⚠️
dwr Dock Worker Robot domain ✅ ✅ ✅
forall Universal quantification testing ✅ ⚠️ ⚠️
rover Mars rover navigation ✅ ⚠️ ✅
satellite Satellite observation planning ✅ ✅ ✅

Legend:

  • ✅ Fully working
  • ⚠️ Known issues (under investigation)

Domain files are located in src/main/resources/repository/.

Integration

As a Library

Create and import a JAR of the SH Planning System. The following methods from the PlanningServices object are available:

// Plan with problem string (domain must be in repository)
PlanningServices.planWithProvidedProblemInString(
  problemToBeSolved: String,
  numberOfPlans: Int = 1
)

// Store domain and problem
PlanningServices.storeProvidedDomainAndProblemInString(
  domainToBeSolved: String,
  problemToBeSolved: String
)

// Plan with both domain and problem strings
PlanningServices.planWithProvidedDomainAndProblemInString(
  domainToBeSolved: String,
  problemToBeSolved: String,
  numberOfPlans: Int = 1
)

// Syntax verification
PlanningServices.checkProvidedProblemInString(problemToBeChecked: String)
PlanningServices.checkProvidedDomainInString(domainToBeChecked: String)

// Plan with stored domain/problem
PlanningServices.planWithGivenDomainAndProblemNameReturnString(
  domainName: String,
  problemName: String,
  numberOfPlans: Int = 1
)

Note: Domain and problem files must be in resources/repository/<domainName>/ directory.

As Web Services

Start the HTTP server:

sbt run
// Then run HTTPServer object

By default, the server runs at http://127.0.0.1:9090. Configure host and port in application.conf.

API Endpoints

Endpoint Method Description Body
/services/status GET Check system status -
/services/syntax-verification/domain POST Verify domain syntax Domain definition (text)
/services/syntax-verification/problem POST Verify problem syntax Problem definition (text)
/services/plan-generation/domain-and-problem POST Generate plan from strings Domain + Problem (text)
/services/plan-generation/problem-in-string POST Generate plan (domain in repo) Problem definition (text)
/services/storing/domain-and-problem POST Store domain and problem Domain + Problem (text)

Example Request:

curl -X POST http://127.0.0.1:9090/services/plan-generation/domain-and-problem \
  -H "Content-Type: text/plain" \
  --data-binary @domain.hpdl

Architecture

Parser Architecture

The system uses a modular parser architecture with three main components:

  1. Language-Specific Parsers: HPDLParser, HDDLParser, SHOP2Parser
  2. Intermediate Representation: IntermediateRepresentation
  3. IR Converter: IRConverter - Converts IR to internal domain model

See PARSER_ARCHITECTURE.md for detailed architecture documentation.

Key Components

HTN Optimization Framework

SH includes a comprehensive 9-stage optimization pipeline that significantly improves planning efficiency:

Optimization Pipeline

The optimization cascade consists of four phases:

Phase 1: Structural Transformations

  • Patterns: Generates methods from operator patterns
  • Typredicate: Converts type predicates to proper type hierarchies
  • Warp: Optimizes method preconditions and task lists

Phase 2: Search Space Reduction

  • Pullup: Removes dead branches with contradictory preconditions (75% reduction)
  • Landmarks: Identifies must-achieve goals for pruning

Phase 3: Advanced Optimizations

  • Look-ahead: Detects inevitable refinements (37.5% reduction)
  • Symmetry Breaking: Reduces search width for symmetric objects

Phase 4: Validation & Cycle Detection

  • Dejavu: Prevents infinite recursion with visit markers
  • Wise: Final validation ensuring domain integrity

Verified Effectiveness

Comprehensive testing confirms optimization effectiveness:

  • ✅ Pullup: 75% dead branch removal in synthetic tests
  • ✅ Symmetry Breaking: Measurable search width reduction
  • ✅ Look-ahead: 37.5% method pruning in test domains
  • ✅ Real-world domains: 76% success rate (13/17 domains)

Usage

Optimizations are automatically applied during domain parsing:

// Automatic optimization with default config
val domain = HDDLLanguageParser.parseDomainToIR(domainFile)
val optimizedDomain = domain.optimize

// Custom optimization configuration
val config = OptimizationConfig(
  enablePullup = true,
  enableSymmetryBreaking = true,
  enableLookahead = true,
  enableDejavu = true
)
val optimizedDomain = domain.optimize(config)

See OPTIMIZATION_FRAMEWORK.md for detailed documentation.

Documentation

Contributing

Contributions are welcome! Please follow these guidelines:

  1. Fork the repository
  2. Create a feature branch
  3. Make your changes with clear commit messages
  4. Add tests for new functionality
  5. Ensure all tests pass: sbt test
  6. Submit a pull request

Adding a New Planning Language

To add support for a new planning language:

  1. Create parser in src/main/scala/org/planx/sh/parsing/<language>/
  2. Implement lexer, parser, domain parser, and problem parser
  3. Convert to Intermediate Representation
  4. Register in ParserFactory
  5. Add test domains in src/main/resources/repository/
  6. Add tests in src/test/scala/org/planx/sh/parsing/

See fetch_instructions tool for detailed instructions.

Testing

Running Tests

# Run all tests
sbt test

# Run optimization tests only
sbt "testOnly org.planx.sh.optimization.*"

# Run specific test suite
sbt "testOnly org.planx.sh.optimization.OptimizationValidationTest"

Test Coverage

  • Validation Tests: 6/6 passing (100%) - Synthetic domains with measurable metrics
  • Real-world Tests: 13/17 passing (76%) - Production domains
  • Unit Tests: Full coverage of optimization components

See RUN_TESTS.md for detailed testing instructions.

Known Issues

Parser Issues

  • rover-hddl: Parser error with inline method syntax
  • deployment-shop2: Parser error (under investigation)

Domain-Specific Issues

  • cafeteria-hddl: Duplicate predicates in source domain
  • deployment-hddl: References undefined predicate unknown
  • cafeteria-shop2: Plan length mismatch (generates 2 steps vs expected 7)

These issues are related to domain specifications, not the optimization framework.

How to Cite

Georgievski, I., Palghadmal, A. V., Alnazer, E., and Aiello, M. SH: Service-oriented HTN Planning system for real-world domains. SoftwareX, 27: 101779. 2024.

@article{georgievski2024sh,
  title={SH: Service-oriented HTN Planning system for real-world domains},
  author={Georgievski, Ilche and Palghadmal, Aditya V and Alnazer, Eyad and Aiello, Marco},
  journal={SoftwareX},
  volume={27},
  pages={101779},
  year={2024},
  publisher={Elsevier}
}

Relevant Literature

  1. Georgievski, I. Coordinating services embedded everywhere via hierarchical planning. Ph.D. Thesis, University of Groningen, October 2015.

  2. Georgievski, I. and Aiello, M. HTN planning: Overview, comparison, and beyond. Artificial Intelligence, 222(0): 124-156. 2015.

  3. Georgievski, I., Nguyen, T. A., Nizamic, F., Setz, B., Lazovik, A., and Aiello, M. Planning meets activity recognition: Service coordination for intelligent buildings. Pervasive and Mobile Computing, 38(1): 110–139. 2017.

  4. Georgievski, I., Nizamic, F., Lazovik, A., and Aiello, M. Cloud Ready Applications Composed via HTN Planning. In IEEE International Conference on Service Oriented Computing and Applications, pages 23–33, 2017.

License

See LICENSE file for details.

Contact

For questions, issues, or contributions, please open an issue on GitHub or contact the maintainers.

Version: 2.1.0 Last Updated: May 2026 Status: Active Development - Optimization Framework Validated

About

No description, website, or topics provided.

Resources

Readme

License

MIT license
Activity

Stars

0 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages