Learning for Planning under Uncertainty

Robots, aircraft and machines rarely behave exactly as planned so AI systems must plan for many possible futures at once. Planning for all of them is expensive, and machine learning can show a planner where to look first. In this project you will teach a planner to learn from small problems and then solve much larger ones faster than before. You will combine machine learning, from graph neural networks to large language models, with the search algorithms that planners use to reason about uncertainty.

Picture of felipe-trevizan.md Felipe Trevizan

4 Nov 2026

Background

Many real-world decision problems involve uncertainty: a robot’s gripper may drop an object, bad weather may close an airport, a machine may break down in the middle of a job. Stochastic Shortest Path problems (SSPs) are one of the main models in AI planning encode and solve such problems [1]. An SSP describes the possible situations (states), the actions available in each state, the probability of each outcome of an action, and a goal to reach. Since we cannot know in advance which outcome will occur, the solution is not a fixed sequence of actions but a policy: a rule saying which action to take in every situation that may arise, chosen so that the goal is reached at minimum expected cost.

The number of possible situations grows exponentially with the size of the problem, so solvers cannot afford to look at all of them. Instead, they search: starting from the initial situation, they explore only the parts of the problem that look relevant, using a heuristic (an estimate of the cost still needed to reach the goal) to decide where to look next [2,3]. The better the heuristic, the less the solver needs to explore. Unfortunately, the general-purpose heuristics available for SSPs are either poorly informed or expensive to compute [2].

Machine learning offers another source of guidance. In deterministic planning, where every action has a single known outcome, learned guidance is now competitive with the best hand-crafted heuristics. Models can be trained to estimate the cost to the goal [4,5], to rank which situations look more promising [6], to identify which actions are worth considering [7], or to suggest directly which action to take [8,9]. More recently, large language models have been used to write programs that solve planning problems [10,11]. A key property of these approaches is generalisation: a model trained on small problems from a domain (say, delivering 1 to 5 parcels) can be applied to much larger ones (delivering 50). Much less is known about learning guidance for planning under uncertainty. Early results show that learned policies can help solvers of probabilistic problems [8,12], but several questions remain open:

  • what is most useful to learn when each action can have several outcomes: cost estimates, rankings, preferred actions, or partial policies;
  • how to train models that account for probabilities and for the risk of reaching dead ends (situations from which the goal can no longer be reached), rather than only the distance to the goal;
  • how solvers should be redesigned so that learned guidance fits in naturally, for example by first choosing which kind of action to apply and only then its details [7].

Aim

This project aims to learn domain-level guidance that makes SSP solvers faster on problems much larger than those seen during training. The guidance is used to prioritise computation, not to replace it: the solver still decides what is returned, so a poor prediction costs time but cannot produce an incorrect policy.

The student will choose a concrete form of guidance and the solver it targets, then design, implement and evaluate the combination on probabilistic planning benchmarks. Possible directions include:

  • learning heuristics or rankings for SSPs using graph neural networks or inexpensive WL-graph features [5,6], with training targets that reflect expected cost and probabilities;
  • extending partial-space search [7] to SSPs, so that learned scores decide which families of actions deserve detailed evaluation;
  • using ASNets, other generalised policies or LLM-generated policies [8,9,10] as proposals that the search refines.

The research questions are which forms of learned guidance pay for their inference cost, how they generalise across the number of objects, initial states and goals within a domain, and where they stop helping. The project scope can be adjusted to suit Honours, Masters or PhD level.

Ideal Student for This Project

  • computer science student with an HD average (or equivalent)
  • excited by AI research, planning and machine learning
  • strong programming skills, ideally Python and C++
  • has taken COMP3620/6320 (Artificial Intelligence) and COMP3670/6670 (Introduction to Machine Learning) or equivalent
  • experience with graph neural networks, PyTorch or LLMs is a plus

Contact

If you are interested, please email Felipe Trevizan (felipe.trevizan@anu.edu.au) with:

  • the type of research project you are seeking (Honours, Masters 12-unit or 24-unit, or PhD)
  • a copy of all your transcripts
  • your CV
  • any questions you may have

References

  1. Mausam and Andrey Kolobov (2012): Planning with Markov Decision Processes: An AI Perspective. Morgan & Claypool.
  2. Felipe Trevizan, Sylvie Thiébaux and Patrik Haslum (2017): Occupation Measure Heuristics for Probabilistic Planning. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS’17).
  3. Johannes Schmalz and Felipe Trevizan (2026): Efficient Constraint Generation for Stochastic Shortest Path Problems. Artificial Intelligence, 354.
  4. Patrick Ferber, Florian Geißer, Felipe Trevizan, Malte Helmert and Jörg Hoffmann (2022): Neural Network Heuristic Functions for Classical Planning: Bootstrapping and Comparison to Other Methods. In Proceedings of ICAPS’22.
  5. Dillon Z. Chen, Felipe Trevizan and Sylvie Thiébaux (2024): Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning. In Proceedings of ICAPS’24.
  6. Mingyu Hao, Felipe Trevizan, Sylvie Thiébaux, Patrick Ferber and Jörg Hoffmann (2024): Guiding GBFS through Learned Pairwise Rankings. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI’24).
  7. Ryan Xiao Wang and Felipe Trevizan (2025): Leveraging Action Relational Structures for Integrated Learning and Planning. In Proceedings of ICAPS’25.
  8. Sam Toyer, Sylvie Thiébaux, Felipe Trevizan and Lexing Xie (2020): ASNets: Deep Learning for Generalised Planning. Journal of Artificial Intelligence Research, 68.
  9. Simon Ståhlberg, Blai Bonet and Hector Geffner (2023): Learning General Policies with Policy Gradient Methods. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning (KR’23).
  10. Dillon Z. Chen, Johannes Zenn, Tristan Cinquin and Sheila A. McIlraith (2025): Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies. In Proceedings of the European Workshop on Reinforcement Learning (EWRL’25).
  11. Subbarao Kambhampati et al. (2024): Position: LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks. In Proceedings of the International Conference on Machine Learning (ICML’24).
  12. William Shen, Felipe Trevizan, Sam Toyer, Sylvie Thiébaux and Lexing Xie (2019): Guiding Search with Generalized Policies for Probabilistic Planning. In Proceedings of the Symposium on Combinatorial Search (SoCS’19).
arrow-left bars magnifying-glass xmark