Research Project: Heuristic Search in Hierarchical Planning

People

Supervisor

Description

This work is about analyzing existing heuristics in Hierarchical Task Network (HTN) planning for properties like admissibility and consistency and analyze their impact on completeness when using A* search. It should be analyzed what to do if there are actions with zero costs and develop techniques that can escape from plateous so that search does not get stuck. Techniques for this already exist in classical (non-hierarchical) planning, so one might be able to simply transfer this.

Goals

  • Analyze all existing HTN heuristics whether they are consistent
  • Analyze the impact of zero cost actions on completeness of A* search

Requirements

  • This is a purely theoretic work, so I expect that you are constantly performing at least on a D level, HD would be much better.
  • You must have sufficient prerequisites in AI planning and search.

Please send me:

  • The course code.
  • The URL of your course.
  • The number of points your course has (i.e., 6, 12, 24, or 24 honours final project). Note that I believe that this project ist most suitable for 6 or 12 points.
  • When you would like to do your project.

Gain

  • Get deeper insight in heuristics and their theoretical properties
  • Get deeper insights in standard search techniques and where they might face problems (like getting stuck in plateaus)

Keywords

  • Artificial Intelligence
  • Planning
  • Heuristic Search

Updated:  10 August 2021/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing