Research Project: On the Influence of Randomness in HTN Search and its Exploitation via Restarts

Project still available?

The project is not yet taken by another student.

It might however be that I don't have capacities left in general. Please check out the main page on research projects to see whether I'm maxed out. (I don't post this here so that I don't have to update all my project descriptions in case I don't accept more students.)

Requirements

• This project can be done as 12 pt project (over two semesters) or as 24 pt Honours thesis. (If really required, 12 pt over one semester might also be possible, but is strongly disencouraged).
• You don't need background on AI planning as learning that in the first two weeks should be easy.
• This is a primarily empirical work, and it requires C++ coding skills as well as the ability to develop and run multiple scripts.
• I don't require any specific mark average like for many of my other projects, but I still hope that the results of this work can be published at least at a B-ranked venue, so please don't take this project if you are not aiming at getting a very high HD mark for it. (And no, this doesn't come for free, this is the result of hard work.)

Project Description

TLDR:

In a very nutshell, your task is to run multiple planners multiple times with different random seeds and evaluate the performance difference thus showing the impact of randomness. In a second step, depending on the outcome, this should be exploited via restarting the respective planer after a certain (well-chosen) time.

The slightly longer version:

The performance of planners performing search depends on many factors, such as deadend detectors, the search algorithm, and quality of heuristics. But if the search space contains millions (or more) of search nodes, some decisions -- i.e., which node to select next -- are bound to be not unique. Some programs are artificially made deterministic by choosing the newest or oldest node as a tie-breaker, but not only is this a doubtful strategy (as this tie-breaker might not always carry a clear semantics), but often such a strategy is not even possible due to lacking information. Since we still need deterministic results and runtime, programs are always made deterministic by always making the same random decision in cases where multiple equivalent options exist. This is done with a random seed, that often can be specified as an input parameter.

Since a search procedure (including the chosen heuristic and all other parameters) never always lead to unique decisions throughout the entire search it would be good practice to call each planner many times and report the average as well as standard deviation. Since time is always limited nobody ever does this -- the experiments would simply take too long. So, currently, it's just not known how well some search configuration actually performs, and which impact randomness has. This should be evaluated in this project.

Thus, the task is to conduct a comprehensive empirical evaluation on a large range of planning problems with multiple state-of-the-art planners. In this evaluation, each planner is however called mutliple times, so that mean and standard deviation can be reported. Depending on these values it shall be investigated whether restarts might be beneficial. I.e., rather than investigating more time for the current search configuration, it could be cancelled and started again with a different random seed.

Note that this endeavor is technically independent of the chosen problem class. This means that the project could both be pursued in the context of classical (i.e., non-hierarchical) or hierarchical task network (HTN) planning. Since I primarily publish in HTN planning and since I am also involved in the development of the state-of-the-art HTN planning systems, I prefer conducting this research for HTN planning systems.

Your task is:

• Conduct a comprehensive empirical evaluation with mutliple planning systems.
• Evaluate the impact of randomness and investigate the potential of restarts.
• Report on the findings (using my LaTeX template for research projects).
• Should the results be promising, assist me in putting together a scientific paper (or multiple ones, based on the number of achieved results) at fitting conference (most likely after the project).

Further Reading

This project is on HTN planning. If you are not familiar with this planning paradigm yet, here are a few notes to get started:

• HTN planning is a planning formalism that's concerned with the step-wise refinement of abstract tasks until a primitive plan is found -- so hierarchical planning is quite similar to formal grammars, where an initial non-terminal symbol is refined into a sequence of terminal symbols. The main differences are that (a) primitive tasks (corresponding to terminal symbols) have preconditions and effects, to not every plan is executable and (b) the means to refine compound tasks (which correspond to production rules from formal grammars) are only partially ordered rather than totally as in formal grammars.
• You find further reading recommendations on my page with resources for students. But please don't invest more than a few minute (if any) before your application, since I don't want you to waste any time before I formally agree to supervise your project.

Specifically for this project my paper "Hybrid Planning Heuristics Based on Task Decomposition Graphs", SoCS 2014 is recommended. You actually don't have to read it, but the table shows the desired values over 50 runs each. All newer papers on HTN planning algorithms and heuristics did not do this anymore.