Student research opportunities
Various Combinatorial Optimisation Problems
Project Code: CECS_42
This project is available at the following levels:
CS single semester, Honours, Summer Scholar, Masters
Supervisor:
Dr Patrik HaslumOutline:
Although research in AI planning aims to construct fully general, domain-independent, planning systems, systems are often evaluated and compared by testing them on a collection of benchmark domains, accumulated over time by the research community. Many of these benchmarks resemble well-known combinatorial optimisation problems, such scheduling/sequencing, allocation, etc., or at least contain parts that do, but each also has its own peculiarities and tweaks. For a majority of benchmark domains, it is known that finding optimal solutions is difficult (NP-hard or worse) while just finding any solution is relatively easy (there exists efficient, and often simple, domain-specific algorithms), providing further evidence that the underlying problems encoded in these benchmark domains are, at heart, about optimisation.
Goals of this project
This project consists in picking up one (or more, depending on project time frame, problem difficulty, etc) of the commonly used planning benchmark domains that encode optimisation problems, and attack the underlying problem using whatever methods/tools seem most suitable, including for example LP/MILP, CSP/COP/SAT, local search methods, or anything else.
The aim is to obtain a better understanding of the problems that underlie planning benchmarks -- how hard are they, in a practical, rather than complexity-theoretical, sense, and what instance parameters determine that hardness? how well do domain-independent planning systems compare, in terms of effectiveness and solution quality, to a domain-specific solution? -- but also to learn something about the different combinatorial optimisation technologies -- how difficult are they to apply to a given problem? which is more suited to what kind of problem?
