Eligibility
=====
All applicants are expected to have (or about to have) a 1st class or 2.1 Honours degree or equivalent. UK/EU students eligible only. Make sure to check the detailed criteria before applying: http://www.strath.ac.uk/dta/furtherinformation/eligibility
Funding Details
=========
The studentship will start in October 2011 and covers University fees (UK/EU students only) plus a student stipend for 3 years (stipend level of c. £13,590 in 2011/12).
How to Apply
=========
Send a CV and covering letter to:
- Professor Derek Long: Derek.Long@cis.strath.ac.uk
- Dr Kerem Akartunali: Kerem.Akartunali@strath.ac.uk
Project Summary
===========
AI Planning is a fundamental technology concerned with generating control sequences for predictable systems in order to maximise efficient use of limited resources, including time, energy, money and so on. Planning is concerned with a specific type of problem: those that demand careful structuring of activities to manage the causal relationships between alternative control actions. This problem is clearly closely associated with optimisation techniques and their applications to combinatorial problems, in particular with integer programming.
Classically, planning has been applied to somewhat abstracted and symbolic representations of problems. In practice, many real applications demand that planners reason about actions that have complex and intricate behaviours, including continuous kinematics, 3d-geometry and combinatorial resource management problems. Recent work by Long, Fox, Gregory and Beck, supported by an EPSRC Grant, has proposed a very new model of planning frameworks that exploits an idea from optimisation (Logic-based Benders Decomposition) and one from the automated verification community (SAT Modulo Theories). The former is a well-established decomposition approach to solve hard optimisation problems, whereas the latter is an approach that allows verification techniques to apply to complex systems with continuous and non-linear behaviour. The combination of ideas has been developed as "Planning Modulo Theories" and it offers a route to dramatically extending the range of application of planning systems and making them much more relevant to significant real control problems.
The fundamental challenges that remain in realising this approach lie in the communication channels between master and sub-problems in the Logic-based Benders Decomposition. To make this effective depends on several potential areas of improvement. The first important area is to establish an efficient mechanism for generating strong "cuts" (or "no-goods"). This will help that can constrain the solutions proposed by the master solver. The second important area is to build a methodology to allow sub-solvers to communicate advice to the master solver that guide it into making effective choices for the sub-solvers.
The student will explore the particular problems in the design of an effective interface between a sub-solver and a master planner, looking at the use of cuts and heuristic relaxations as means for communication between the systems, where knapsack and lot-sizing problems will provide the initial practical examples. This will lay the foundation for important developments in the general design of the generic problem-solving framework and its application to a range of real problems.
===============================
Dr. Kerem Akartunali
John Anderson Research Lecturer in Optimisation
Dept. of Management Science
University of Strathclyde
Graham Hills Building, Rm 873
40 George Street
Glasgow G1 1QE
United Kingdom
Tel (work): +44-141-548 4542
Tel (mobile): +44-776-869 5448
Web: http://personal.strath.ac.uk/kerem.akartunali/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
