Maximising Efficiency of Resource Usage Under Uncertainty in AI Planning

8bc0db3b-9396-4346-b91b-89dc67bed950

Closed

EPSRC
EPSRC
EPSRC
EPSRC
EPSRC

£517,525

Nov. 1, 2011

April 30, 2013

In recent years planning technology has a enjoyed significant increase in real-world application, with industry and general science research benefiting from the great depth theoretical work done in this area over many decades. The core problem of deciding which activities to carry out and when occurs in a vast range of domains; the research area of planning is concerned with developing generic problem solving technology that automates the task of performing this core reasoning. Planning technology has been employed in a wide range of domains including controlling printing presses, power management for the UK National, train scheduling on the Hungarian Railway Network, scheduling aircraft landing in airports, and autonomous robotic control, both in space and in the oceans. Experience in these areas has given rise to two key observations. First, the existing theoretical work done in AI Planning has been extremely valuable, allowing planning technology to begin to solve real world problems. Planning is a fundamental component of intelligent autonomous behaviour and as such planning technology has real potential for application in many different areas, both now and in the future. The second is that whilst one can observe that planners can now begin to be applied to these problems, there is still a great need for improvement of the underlying technology, in terms of expressivity and performance, in order to be able to create greater autonomy by allowing reasoning about an uncertain world.At the heart of this lies deeply theoretical computer science research: a planner is a generic problem solving system, consisting of search algorithms and heuristics. Of particular interest is reasoning about time and resources, something key to many areas of computer science, from compilers and programming languages to web services and optimisation. In order to tackle application problems well, reasoning effectively about these is essential. Of specific interest here is uncertainty in time taken and resources consumed. This occurs in many application domains, and in each of these a similar approach is taken: conservatism about time and resource availability in order to guarantee success. This, however, comes at a cost. By way of example, when planning for autonomous Martian exploration, the models used by both the ESA and NASA are pessimistic, underestimating the amount of power the rover will receive from the sun, and overestimating the amount of energy and time each activity will take. The result is that the equipment is highly under-utilised, with fewer science targets being achieved than could have been with better on-board reasoning. Given the expense of placing rovers on Mars and the limited equipment lifespan, this is a great cost to mankind's exploration of space. A similar problem occurs when deploying renewable energy generation: wind farms are assumed to provide 10% of their maximum output, even thought the reality is almost always greater than this. This conservative assumption, there to ensure power is always provided, causes great environmental and economic cost, as extra production capacity must be available through other sources regardless of whether it is required.The major benefit of planning is in generating a generic problem solving technology. Developing several bespoke solvers would take many years, and incur great financial cost. By developing efficient planning systems, a single domain-independent problem-solving core is built, capable of solving many problems without the cost of developing a bespoke solver for each. The core of this research is addressing challenges in solving the general planning problem that will allow future application of planning, extending the range of problems to which this generic technology can be applied.

Potential Impact:
Here we consider the wider impact of this research on society and industry; this is subject to varying time-scales, with some areas expected to benefit within the lifespan of the project, and other benefits to become apparent in the longer term. Planning is generic problem solving technology, with the potential for impact on many different application areas. The UK has established itself as a world leader in planning technology on the international scene, and we are already exporting this technology to the US and Europe. This project will help the UK to maintain its leading role in applications of planning, by developing the technology to allow further pioneering deployment in a range of different areas. The fellowship provides the opportunity for a young researcher, who has shown great promise, to stay in the UK to pursue this world leading research, thus preventing brain drain and maintaining expertise within the UK. Supporting a young researcher will clearly have a great impact on career development, nurturing an independent research career. Environmental protection is a leading priority across the world at the current time, with governments, including that of the UK, aiming to meet emissions targets. This is the key reason I have chosen to focus on wind farm planning, an application in the area of smart grids. When planning power generation in a setting with renewable and non-renewable energy sources, many sources of power are available, from wind-farms, to hydroelectricity, to nuclear power, to coal/gas power stations. The challenge is to automatically adapt to meet customer demand under uncertain weather conditions whilst making the best use of renewable, low emission power sources. Research in this area can directly reduce the UK's use of non-renewable and environmentally damaging generation sources, helping the government to meet targets, and improve global environmental protection. A further potential application is in micro-generation --- effectively, small-scale power grids amongst networks of homes --- and smart electricity meters, running high energy appliances during times of surplus production. The work done in the project will be directly applicable to these problems. These applications in power engineering have clear potential to directly benefit UK industry. The power supply industry is one of the largest in the UK, with the relevant companies, e.g. National Grid PLC, standing to benefit, both by achieving environmental targets, and through cost reduction by efficient use of resources. This in turn benefits the UK, establishing a cheaper energy supply, helping all UK businesses, as well as establishing the UK as a technological leader in energy production and distribution. Optimisation planning under uncertainty is core to many businesses (for example logistics firms, oil supply companies, airports): making the best use of finite resources. In the longer term, small businesses will be able to benefit from planning research: these companies also need to optimise resource usage, but writing a bespoke problem solving system is expensive; using an off-the-shelf problem-independent technology allows this to be done at at much lower cost. Research being done into intuitive modelling technologies for planning, and development of planning technology, will make this possible in the future. Autonomy is important to allow tasks to be carried out that either pose too great a risk to human life, or simply that the costs of the manpower required to perform such tasks would be prohibitive. Examples of such tasks are nuclear decommissioning, search and rescue following disasters, space and oceanographic exploration and autonomous assistance to help our ageing population to remain independent for longer. These are long-term beneficiaries that will be reached through the continued efforts of the planning community, as well as improving technology.