ASAP Research Themes

Research Themes

Here is a list of the research themes that underpin the overall research strategy of the group. Click on them for an overview of the research and related theme/projected resources.
Our Externally Funded Projects.


Methodology	Applications
Machine Learning and Data Mining. Machine Learning, or how to construct programs that automatically learn from experience is a core component of Artificial Intelligence. Its aim is to identify patterns in data and construct some knowledge (e.g. rules, decision trees, support vectors) that model this data. Some of its applications include medical diagnosis, bioinformatics, stock markets predictions, search engines, recommendation systems, etc. and, in general, any kind of prediction. Data Mining deals with the extraction of knowledge from vasts amounts of data. It contains machine learning as one of its main core components. While machine learning aim is to obtain accurate models, data mining is more focused on knowledge discovery. That is, providing the users with new insight about the data being mined.	Bioinformatics and Systems/Synthetic Biology. Bioinformatics is a research field where many disciplines of science such as mathematics, computer science, engineering, etc. are put together to solve biological problems and bring new insight into our understanding of how life works. Advances in the last two decades in biological technology provided us with vasts amounts of data about many aspects of life (for instance, the Genome project). However, we only have a limited understanding of all this data. Computer technology, mathematics, engineering provided the tools to bring new insight in all this data, creating the Bioinformatics field. Closely related to Bioinformatics is Systems Biology. The focus of systems biology is the principled study and modelling of the functioning, interactions and dynamics of biological systems and at different scales and places (e.g. inside a cell, across organs, metabolic systems). This principled study draws its inspiration in multiple disciplines such as mathematics, computer science and engineering. Bioinformatics and systems biology aim at bringing new light and understanding of biological systems. The aim of synthetic biology is to use this knowledge to design new biological systems.
Intelligent Multi-agents. We apply intelligent multi-agent systems as a technology to solve problems in an increasingly wide range of complex applications. These systems are inspired by models from biology (ecosystems) and economics (markets). They represent a new way of analysing, designing, and implementing complex software systems.	Economics and Game Strategy. Decision making is an essential topic of interest within the research communities of both artificial intelligence and economics. This is the reason why some classic methodologies in economics, utility theory for example, have been applied by the researchers in the fields of computer science to build intelligent agents. In the ASAP group we investigate the problems of decision making at both individual level and group level, and seek for interdisciplinary applications of the approaches in economics. We also conduct research on computers that can play games at levels approaching, or above, that of humans and to research ways in which the underlying patterns in economics can be learnt and exploited.
Cooperative Heuristic Search. We investigate a variety of mechanisms to promote the cooperation between heuristic methods when tackling difficult search and optimisation problems. The purpose is that the heuristic methods exchange meaningful information at the right times during the search so that the performance achieved is better than simply adding the search effort from the various methods. It is expected that cooperation helps the different heuristics to build some form of knowledge regarding the global search process and this knowledge helps to improve their individual search process. Among the issues that we investigate are the following: 1) mechanisms for communication and memory sharing among heuristic methods and possibly also exact algorithms, 2) issues arising from the multi-thread implementation of heuristic methods, 3) cooperative mechanisms within hyper-heuristics for two purposes: one is the selection of heuristics according to problem and search status, the other is the automated generation (evolution) of heuristics for a given problem.	Educational Timetabling. In educational timetabling problems, a set of exams, courses or project presentations, etc. need to be scheduled into limited resources including rooms within a certain number of time periods. A number of constraints of different importance, which are usually different in different institutions also need to be satisfied. In ASAP group, we investigate a wide range of algorithms in meta-heuristics and different techniques concerning multi-objective and constraints handling, etc in educational timetabling problems. One of our research directions is to explore approaches that can operate at a higher level of generality than what the current timetabling system can support.
Artificial Intelligence. Artificial Intelligence (AI) research within the ASAP group has two main objectives. One is the application of AI techniques in various domains, in particular, solving hard optimisation problems. The other objective, which reflects the nature of artificial intelligence, is the development of new methodologies and novel computational techniques for the creation of human-like intelligence.	Intrusion Detection. The central challenge with computer security is determining the difference between normal and potentially harmful activity. For half a century, developers have protected their systems by coding rules that identify and block specific events. However, the nature of current and future threats in conjunction with ever larger IT systems urgently requires the development of automated and adaptive defensive tools.
Case-Based Reasoning. As a knowledge based methodology, CBR solves problems by reusing knowledge for solving previous similar problems. The knowledge is modeled and stored as cases in the reasoning system. We investigate CBR techniques to solve complicated scheduling problems including personal scheduling and timetabling problems. Not only solutions themselves are reused, but also are previous heuristics in similar problem solving situations reused for solving different scheduling problems.	Medical Optimisation. Medical optimisation is the scientific field that deals with the storage, retrieval, sharing, and optimal use of biomedical information, data, and knowledge for problem solving and decision making. It touches on all basic and applied fields in biomedical science and is closely tied to modern information technologies, notably in the areas of computing and communication.
Discrete Event Simulation. We investigate discrete event simulation to solve complex problems in stochastic systems by gaining insight into their behaviour for a better understanding of their operation.	Personnel Scheduling. Personnel scheduling problems are found in a wide variety of environments. Some of the most complex and challenging problems arise in hospitals and healthcare centres, for example nurse and physician rostering. The benefits of automating the rostering process in these situations include reducing the planner's workload and associated costs and being able to create higher quality and more flexible schedules. This has become more important recently in order to retain nurses and attract more people into the profession. Better quality rosters also reduce fatigue and stress due to overwork and poor scheduling and help to maximise the use of leisure time by satisfying more requests. A more contented workforce leads to higher productivity, increased quality of patient service and a better level of healthcare. The ASAP group has developed a number of novel and very effective rostering algorithms in real world scenarios. These approaches include tabu search, variable neighbourhood search, memetic algorithms, case-based reasoning, hyperheuristics, hybrid methods and many others. In order to scientifically test and validate these algorithms we have created a suite of highly challenging benchmark data sets from a number of hospitals around the world. These data sets are publicly available at http://www.cs.nott.ac.uk/~tec/NRP/. This collection is the only source of a wide range of real world nurse rostering benchmark instances and a valuable asset of the personnel scheduling community.
Evolutionary Algorithms. We investigate on a wide range of evolutionary techniques such as genetic algorithms (GA), genetic programming (GP), memetic algorithms (MA), multiobjective evolutionary algorithms (MOEA), scatter search (SS), ant systems (AS), etc. to solve complex planning, optimisation and search problems. We investigate the working principles of evolutionary algorithms when applied to a range of problems in order to better understand their behaviour in different scenarios.	Production Scheduling/Re-scheduling. Real world production scheduling problems, which require the efficient allocation of jobs onto machines, are notoriously complex: machines are many and of different characteristics, workers get sick, new jobs arrive to the shop floor, machines break down, etc. Moreover, the case where two or more objective functions have to be optimised simultaneously is often present. Under these circumstances, classical optimisation methods are usually insufficient and, in order to be successful, scheduling systems have to make use of modern artificial intelligence (AI) based techniques. ASAP is a leader in the investigation, design and application of AI techniques, including evolutionary algorithms and hyperheuristics, hybridised with fuzzy systems and multi-objective optimisation approaches, to the scheduling and rescheduling of production shops. Algorithms developed by ASAP have been successfully applied to a wide variety of problems that emerge, among others, from steel production, printed circuit board assembly, cardboard box manufacturing and the printing industry.
Fuzzy Systems. Fuzzy systems is an alternative to traditional notions of set membership and logic. Many decision-making and problem-solving tasks are too complex to be understood quantitatively, however, people succeed by using knowledge that is imprecise rather than precise. We use this technology in application areas such as medical optimisation and production scheduling.	Radiotherapy Planning and Scheduling There are two stages in radiotherapy. A diagnostic phase and, the radiotherapy treatment phase. During the diagnostic phase patients go through a series of tests. These tests depend on the cancer site and follow certain order. One of their outcomes is to generate a fractionation scheme which is followed during the radiotherapy treatment phase. In radiotherapy scheduling we are interested in assigning appointment slots for the complete patients' care pathway whilst optimising patients' waiting times and satisfying precedence constraints amongst operations, organizational constraints, etc. This is a complex real-world scheduling environment which calls for novel operational research approaches.
Heuristics and Metaheuristics. A heuristic is a "rule of thumb", a method for making an educated guess at the solution of a problem. Many real problems are too complicated with too large a search space to be solved exactly within realistic timescales, lacking the structures required to allow mathematical programming methods to be utilised effectively. However, there are often some underlying structures to real problems such that good solutions are similar to other good solutions in some manner. These structures can often be utilised to allow a 'good guess' at a good solution to a problem. To illustrate the common usage of a heuristic solution method consider the method that a traveller may use to determine the path to follow to head from the south side to the north side of a strange city. Every time a junction is reached a decision has to be made about the route to take from that junction. In the absence of signs or a map, a sensible heuristic may be to always take the path which has a direction that is the closest to north. Given road layouts, this may not actually be the most direct route to follow, but will often enable the traveller to get to their destination in a reasonable fast manner. A metaheuristic (from the Greek `meta' meaning `beyond') consists of a higher level strategy imposed upon lower level heuristics. In the earlier example of selecting a route at each intersection, this could involve adding a controlling strategy to avoid backtracking or cycling (repeating a previously travelled route), or to take account of higher level information to provide additional guidance. The introduction of such a strategy could, for example, help the traveller to avoid the situation where the most northerly path doubles back on itself. The most common metaheuristics include Tabu Search (where a memory is used to improve the search) and Simulated Annealing (where a small (and decreasing) chance to make a seemingly bad decision can be used to avoid cycling or stagnation. We use and explore metaheuristics (and hybrids of heuristic and exact search methods) to solve a wide range of complex combinatorial optimisation real world problems.	Robotics In the ASAP Research Group we see robots as tools which let computers interact with the world around them. A functioning robot requires technology and software from many different fields to be brought together. We work with researchers from several other groups worldwide with many different technical backgrounds. Our aim is to collect problem-solving techniques from other areas of science and apply them to robotics. Examples of current robotics projects include: the development of a robotic 'security guard' using software from the field of artificial immune systems; and an exploration of operational research algorithms using robots to provide physically realistic scheduling scenarios..
Hyper-heuristics. A hyper-heuristic is a heuristic search method that seeks to automate, often by the incorporation of machine learning techniques, the process of selecting, combining, generating or adapting several simpler heuristics (or components of such heuristics) to efficiently solve computational search problems. Hyper-heuristics can be thought of as "heuristics to choose heuristics". One of the motivations for studying hyper-heuristics is to build systems which can handle classes of problems rather than solving just one problem. The idea is to automatically devise algorithms by combining the strength and compensating for the weakness of known heuristics. In a typical hyper-heuristic framework there is a high-level methodology and a set of low-level heuristics (either constructive or perturbative heuristics). Given a problem instance, the high-level method selects which low-level heuristic should be applied at any given time, depending upon the current problem state, or search stage.	Space Allocation. In many educational institutions both office and teaching space are hard to manage, and often end up used inefficiently. This results in costs being higher due to space ending up unused, and yet paradoxically the users feeling that there is insufficient space. The aim of this theme is to provide decision support methods, and the associated scientific foundations, for improving space management and planning in general. In the ASAP group we investigate heuristic optimisation techniques to produce high quality solutions to the class of space allocation problems, such as shelf space allocation, office space allocation and teaching space allocation. We also develop rich models for space allocation problems that take into consideration the great variety of requirements and constraints that exist in these problems.
Multiobjective/Multicriteria Methods. We investigate multi-objective optimisation and multi-criteria decision-making to solve a range of multiple objective scheduling and timetabling problems. Our aim is to explore the nature of different constraints of these problems and to present them within a multi-objective framework; to investigate the applicability of different multi-objective approaches in order to obtain improvements; to develop applications and adaptations for real world problem situations, involving dynamically changing situations over time. We also develop effective and efficient metaheuristic methods for tackling complex multi-objective combinatorial optimization problems. The main metaheuristic methods used in our research include evolutionary algorithm (EA), Simulated Annealing (SA), Tabu Search (TS), Ant Colony Optimization algorithm (ACO), etc. Some challenging ideas in multi-objective optimization will be highly investigated in improving the effectiveness and efficiency of multi-objective metaheuristic methods. Particularly, we are more interested in applying these methods to solve real-life multi-objective scheduling and timetabling problems.	Stock Cutting/Packing. We are conducting research into a variety of stock cutting problems. These include the knapsack problem, regular and irregular 2-dimensional nesting, and other stock cutting variants. We are looking at placement algorithms, case-based reasoning approaches and other current techniques to solve such problems whilst also developing new heuristics and metaheuristics to reduce the size of the search space and produce good solutions. Our research is particularly relevent to the manufacturing industry, so we are closely working with a local company so that our research can be implemented for real world applications.
Systems Self Assembly. Self-assembly is a process in which there are specific local interactions and constraints between a set of components. During the self-assembling process, components will autonomously assemble into the final desired structure through an exploration of alternative configurations. Neither central control mechanism nor external assistance is needed during this process.

Comments to jds@cs.nott.ac.uk