Diagnosis and planning are model-based AI technologies. Although originating in AI, diagnosis and planning are both optimisation problems: diagnosis seeks the best explanation of given observations, while planning seeks the best plan of action to achieve given goals. Both use models of (typically discrete state, discrete event) dynamical systems. But because both are model-based, they apply to any problem that can be formulated as a diagnosis or planning model. For example, we can make hypothetical “plans” for reaching the current state, to explain how it may have evolved. Planning and diagnosis can be general-purpose problem-solving technologies.
Project Focus
Bringing Optimisation into Planning
Planning is inherently an optimisation problem: plans of good quality tend to be hard to find, and plans found easily tend to be poor. Yet, a lot of planning research targets one of the two ends of the efficiency-quality spectrum. Much work has gone into devising fast planning algorithms, resulting in systems able to scale up to very large problem instances, but which completely disregard the quality of plans. Planners that guarantee solution optimality, on the other hand, are not capable of scaling anywhere near as far.
We are developing new planning methods that aim to fill this gap, offering greater flexibility to trade off planning time and plan quality. This means both finding better plans given more time, but also proving better bounds on plan quality – in other words, shrinking the optimality gap. To do this, we draw on ideas that have been successfully used to solve other optimisation problems, like large neighbourhood search [IJCAI 2013; AI 2012] and incremental constraint generation [ICAPS 2012a; ICAPS 2012c].
Planning into Hybrid Systems
Current AI planning methods are most effective for dealing with system models that have finite, discrete states and discrete actions. Planning research has long sought to extend its reach to more expressive system models, including non-finite (numeric) state variables, time constraints on actions, etc. Such additions make planning problems harder to solve – even basic numerical planning formalisms are undecidable, and few if any planners for such problems can guarantee plan optimality. However, we can identify important classes of planning problems that require limited hybrid reasoning (for example, switching problems in power networks involve discrete actions that alter the behaviour of a continuous system) to which we can systematically extend classical planning techniques [ICAPS 2014a].
One key idea for hybrid planning is integration of different solver technologies. There are effective solvers for many kinds of optimisation problems (e.g., mixed integer, linear and non-linear programming), which we can combine with planning methods, either using one within the other [ICAPS 2014b] or by specialising solvers to work more effectively on encodings of planning problems.
A Spectrum of Diagnosis Algorithms
Automated diagnosis is studied in several research communities (AI, control). Diagnosis problems differ in their modelling framework (e.g., whether systems are static or dynamic, discrete or continuous), and traditionally, different methods have been applied to these model classes. Yet, most diagnosis algorithms can be broadly classified into three approaches (based on belief state tracking, characterising fault modes, or performing consistency tests), regardless of the modelling framework.
We study the basic algorithmic principles of diagnosis, leading to a better understanding of the diagnosis algorithm design space, and to novel solutions by taking ideas across model-class boundaries. As an example, our use of the consistency-based approach for diagnosing discrete-event systems (which have traditionally only been tackled with state-tracking methods) resulted in an algorithm with far better performance on alarm processing problems [DX 2011a; KR 2012; DX 2013].
Diagnosis for Decision Support
In many application areas, the role of automated diagnosis will be primarily as a supporting tool for human experts. That places demands on diagnosis systems to do more than just identify the most likely fault: to gain people’s trust, they will need to be able to explain the reasoning behind the diagnosis. On the other hand, working in tandem with human system operators also means that the diagnoser does not have to be omniscient: the role of automated diagnosis can be to handle routine monitoring and easily identified, non-critical faults, leaving the diagnosis of intricate fault situations to experts.
We are exploring the use of automated diagnosis for alarm processing. Faults in large systems, such as power or telecomm networks, frequently give rise to “alarm cascades”, when the original fault causes a range of secondary abnormalities, all of which generate multiple alarms. The goal of intelligent alarm processing is to help operators sift out the crucial information from the alarm flood, for instance by grouping alarms that can be diagnosed to have the same underlying cause [DX 2011b].
