Student research opportunities
Efficient Cost-Bounded Search and Planning
Project Code: CECS_797
This project is available at the following levels:
CS single semester, Honours, Summer Scholar, Masters
Supervisor:
Dr Patrik HaslumOutline:
Many planning problems require solutions that meet hard limits: a project must meet its budget, a daily schedule cannot fill more than 24 hours, an airplane carries a limited amount of fuel, and so on. Finding solutions to such bounded problems is different from traditional optimisation: the objective is not to find the best solution (i.e., the one that uses the least time, money, fuel, etc), but to find any acceptable solution (i.e., one that is within the bound), and to find it as quickly as possible.
Recently, some new heuristic search algorithms for solving such cost-bounded problems have been proposed (see references below). But there are many questions still to answer: What is it that makes these algorithms effective? What kinds of problems will they fail on? And are there in fact simpler algorithms that can achieve equally good results?
Goals of this project
The aim of this project is to test a wide variety of heuristic search algorithms for bounded-cost planning. It involves some implementation (building on existing frameworks for heuristic search planning), but most of all experimentation, using a wide range of different planning problems. It may also be necessary to design new, artificial, problems to test specific hypotheses about the interplay between the structure of the search space, the heuristics used, and the search algorithms.
Requirements/Prerequisites
A basic understanding of heuristic search is advantageous.
Background Literature
Roni Stern, Rami Puzis, Ariel Felner. "Potential Search: A Bounded-Cost Search Algorithm". ICAPS 2011 (PDF)
Jordan Tyler Thayer, Roni Stern, Ariel Felner, Wheeler Ruml. "Faster Bounded-Cost Search Using Inadmissible Estimates". ICAPS 2012 (PDF).
