A classical AI planning project implementing a planning graph and heuristic search analysis for an Air Cargo logistics domain. The project explores how different search strategies scale as the planning domain grows, and evaluates the trade-offs between node expansion, runtime, plan quality, and heuristic informativeness.
This repository presents the work as a compact, professional portfolio project in symbolic AI, automated planning, and search-based decision systems.
The project builds and evaluates a forward-planning agent for solving Air Cargo transportation problems of increasing complexity. It combines:
- classical state-space search;
- planning graph construction;
- mutex reasoning between actions and literals;
- planning-graph heuristics;
- empirical comparison of search algorithms across progressively larger domains.
The implementation focuses on the core mechanics behind planning graphs, including action mutexes, literal mutexes, and heuristic estimates derived from planning graph levels.
The project implements the key components of a planning graph:
- inconsistent effects detection;
- interference detection between actions;
- competing needs detection;
- inconsistent support between literals;
- negation-based literal mutexes;
- automatic graph expansion until the graph levels off.
The planning graph supports three heuristic estimates:
h_levelsum— sums the first level at which each goal literal appears;h_maxlevel— returns the maximum first-appearance level among the goals;h_setlevel— finds the first level where all goals appear without pairwise mutexes.
These heuristics are used to compare informed planning strategies against uninformed search.
The experimental report compares multiple search configurations, including:
- Breadth-First Search;
- Depth-First Graph Search;
- Uniform Cost Search;
- Greedy Best-First Search;
- A* Search;
- simple goal-count heuristics;
- planning-graph heuristics.
The report evaluates four Air Cargo planning problems with increasing numbers of grounded actions:
| Problem | Grounded actions |
|---|---|
| Air Cargo 1 | 20 |
| Air Cargo 2 | 72 |
| Air Cargo 3 | 88 |
| Air Cargo 4 | 104 |
The experiments show a clear scalability pattern:
- uninformed search expands rapidly as the domain grows;
- greedy best-first search with lightweight heuristics remains extremely fast;
- planning-graph heuristics can reduce node expansions substantially;
- richer heuristics may become expensive because the planning graph must be built and evaluated repeatedly;
- optimality depends strongly on the search algorithm and admissibility of the heuristic.
For example, Uniform Cost Search grew from 60 expansions on the smallest problem to more than 113,000 expansions on the largest problem, while Greedy Best-First Search with h_unmet_goals remained below 30 expansions on the tested large problems. A* with h_pg_levelsum reduced the number of expansions sharply, but at the cost of much higher runtime on the largest domain.
.
├── my_planning_graph.py # Planning graph implementation and heuristics
├── Report.pdf # Experimental report and analysis
└── README.md # Project documentation
Depending on how the full project is restored or extended, additional files may include the planning problem definitions, search algorithms, tests, and domain utilities.
This project demonstrates practical understanding of:
- symbolic AI;
- automated planning;
- planning graphs;
- GraphPlan-style reasoning;
- mutex propagation;
- heuristic search;
- A* and greedy best-first search;
- search-space scaling;
- empirical algorithm evaluation;
- trade-offs between optimality, runtime, and heuristic cost.
This repository uses GitHub Actions to run basic Python validation on each push and pull request. The workflow checks that the code compiles successfully and runs pytest automatically when a tests/ directory is present.
Although this project originated from an academic AI planning exercise, it illustrates a broader engineering question: how should an intelligent system choose actions under constraints when exhaustive search becomes expensive?
That question is relevant far beyond Air Cargo toy domains. The same conceptual trade-offs appear in:
- logistics and routing;
- autonomous systems;
- mission planning;
- decision-support tools;
- agentic AI systems;
- resource-aware automation;
- AI systems operating under uncertainty.
The project is therefore presented not merely as a course artifact, but as a small, inspectable example of classical AI planning and heuristic decision architecture.
Potential extensions include:
- adding a clean command-line interface;
- packaging the project with reproducible experiment scripts;
- adding unit tests for mutex and heuristic behavior;
- exporting results to CSV;
- generating plots automatically from experiment logs;
- comparing additional heuristics;
- adding visual planning graph diagrams;
- adapting the planning framework to a modern logistics or mission-planning scenario.
This project is released under the MIT License. See LICENSE for details.
Created by Sabrina Palis as part of an applied AI portfolio focused on symbolic reasoning, heuristic systems, decision-support architectures, and practical AI education.