AI Planning with Continuous Non-Linear Change

Intelligent autonomous systems have a significant role to play in meeting the increasing needs of a growing modern society. These systems can take many forms. Autonomous robots can assist humans in performing tasks, work in manufacturing, and play an important role in cleaning up or exploring environments too hostile for humans. Autonomous large scale software systems can control our over-subscribed transport and power networks, allowing us to operate them as efficiently as possible to serve the growing population.

In order for an autonomous system to act intelligently and achieve its goals, it needs to be able to plan, that is decide what actions to take and when to take them: this is the problem of Artificial Intelligence (AI) planning. The major research goal for AI planning is to create systems that are domain-independent, that is they are not human-programmed to solve one specific problem; but rather are general purpose and capable of planning in scenarios encountered across a wide range of applications.

Decades of research has produced increasingly capable AI planners, and there have been successes in using these in a diverse range of applications, including the planning of global ocean liner movements and security penetration testing. There are, however, still major challenges to be met in creating systems that are scalable and expressive enough to form the core of the AI systems needed to meet future societal challenges. One major challenge, and the focus of this project, is equipping planners with the expressive capability to reason about a complex and dynamic world. Many interesting target problems, such as nuclear clean up or traffic control, require not only conventional reasoning based on facts that are true and false; but also reasoning about non-linear continuous dynamics: radiation exposure or traffic flow.

This project addresses the challenge of creating a planner capable of reasoning with non-linear continuous dynamics alongside all the existing state-of-the-art capabilities of the most expressive modern planners (time, deadlines, soft constraints and cost optimisation) without significantly compromising scalability. Such a system will be an invaluable asset in controlling the autonomous systems of the future.

The research challenges that need to be addressed to achieve this are significant, as present techniques for reasoning with these problems make compromises in one way or another. Some techniques are limited in scalability due to a requirement to 'discretise' time, splitting it into small chunks, and reasoning about whether to do something every fraction of a second. Others are incompatible with other expressive features; or rely on technologies that support only linear change. In this project we build on OPTIC, a planner that supports only linear change, due to its support of other expressive features and good potential for scalability.

We will address the challenges of reasoning with non-linear change in a linear framework by reasoning with piecewise-linear approximations of the continuous change. The main challenges here are determining how to integrate reasoning about these with existing techniques for expressive reasoning; and generating sufficiently accurate approximations automatically. The finer we make the approximation, the more points we have to reason about and the harder it is to solve efficiently; yet approximations that are not fine enough will not permit us to solve the problem.

Throughout the project, alongside development of the planner, we will focus on creating models of target problems, guided by our contacts with organisations in the relevant fields. These will allow us to ensure our work remains focussed on addressing the challenges that will most benefit application as well as providing us with benchmarks against which we can evaluate the project. Our target applications include nuclear clean up; medical dose scheduling and traffic flow management.

The domain-independent nature of AI planners leads to great scope for application in a wide range of areas. The UK is already a world leading centre for AI Planning research, this project will consolidate this and develop even more capable technology, to move towards addressing major future economic and societal challenges.

Within this proposal we have identified three key areas of national interest to which the project can contribute, and have a dedicated domain acquisition work package to explore the requirements of these problems through visits to relevant organisations:

-Traffic Control Planning: the UK road networks are increasingly overcrowded leading to high levels of congestion and pollution. AI planning has real potential in this domain, as evidenced by recent successes; however, in order to do better and to help to address this challenge fully more accurate reasoning about the non-linear continuous dynamics of traffic flow is needed.

-Nuclear Decommissioning: management and clean-up of radioactive waste is a huge challenge at sites such as Sellafield, due to the UK's nuclear legacy. This is carried out by humans and in order to enforce strict radiation exposure limits very specific plans are made for their activities at at the radioactive site. Such plans are currently generated by hand, but this could be automated by a system capable of reasoning with non-linear exposure levels. This is also an important step towards effective robotic clean up in areas with higher radiation levels, such as Fukushima.

-Control of Power Networks: the challenges faced in the National Grid are planning effective use of generation facilities to deal with the fluctuating output of renewable energy production, which is often dependent on the weather; and maintaining a stable and safe state in the network in response to changes in demand or generation. There has been much research into applying AI technologies in this area, including some of the PI's own work, but there are still open challenges. The inherently non-linear dynamics of power systems means that they are a good target application for this project.

Planning also has much to contribute to the economy. Businesses often have to manage large fleets of vehicles (e.g. logistics firms) or plan efficient use of limited resources (e.g. airport management or train tracks). The PI has already been involved in a successful project using AI planning to determine efficient repositioning of ocean liners, in collaboration with ITU Copenhagen and MAERSK. Efficient operations planning is a challenge for humans, and inefficiency costs thousands of pounds. Allowing reasoning about non-linear dynamics, and even non-linear cost functions, will extend the scope for application of AI planners in large-scale operations planning.

For small businesses in need of effective problem solving and planning solutions the cost of hiring expert software developers is prohibitive; an off-the-shelf domain-independent planner can help here. During this project the founder of a new tech start up 'Medic' will be working as an MSc student in the Planning group at King's. The start up aims to provide effective guidance on dose timings for combined drug therapies, based on plasma concentration levels. The MSc project will focus on making AI planning models of this problem. These will provide useful benchmarks, a route to impact in healthcare, and valuable insights into the use of planning in a small business.

Finally, physical robotic systems will play a major role in future society and, in order to act intelligently and autonomously, they need to be able to plan their activities. These systems are particularly valuable in situations that are too remote or dangerous for humans, for example, in space, deep ocean exploration and search and rescue scenarios. They also have an important role to play in supporting human activity, for example, the potential for robotic assistants to support the elderly.