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.)
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:
This project is on HTN planning. If you are not familiar with this planning paradigm yet, here are a few notes to get started:
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.