Numeric Domain Model Acquisition from Action Traces

Many industrial and commercial applications of planning technology have to reason about numbers. For example, in the area of autonomous systems and robotics, an autonomous robot often has to reason about its position in space, power levels and storage capacities. We call the internal representation that the robot has of its environment its model of the world. It is essential for these models to be easy to construct and ideally, they should be automatically constructed.

This project concerns the subject of learning formal models of state-transition systems from observation of those systems operating. Consider an observer unfamiliar with the game of chess: by observing a sequence of moves, much can be learnt about the rules of the game. Watching a bishop for long enough demonstrates that only diagonal moves are possible for this piece.

Domain model acquisition, or automated modelling, is the problem of allowing a computer to learn its own world model by observing actions. We will develop new methods of automated modelling for state transition systems with numeric state variables. And when we refer to domain model acquisition, we refer to the learning of any state transition system from example data that includes sequences of state transitions, whether that is in the context of automated planning, general game playing, interactive narrative, workplace rostering, or any other type of underlying problem.

We first plan to learn models of domain with a common restriction of numeric variables in planning; the restriction to action costs. This restriction means that each ground action has a constant cost, and that the only numeric variable accumulates the sum of these individual action costs over the length of the plan. This accumulated value is the optimisation variable. Board games with action costs are those in which a score is accumulated throughout the play of the game.

Successful completion of the first stage means that we have a domain model acquisition algorithm to learn models that include action costs. This class of planning domains is an important subset of numeric planning domains. However, many planning domains contain more complex numeric properties and, in particular, arbitrary numeric variables and constraints. The second stage, therefore, will concentrate on developing algorithms to learn these constraints.

Completion of the project will allow models of many different problems to be learnt simply from observation. Examples include such things as capacity limits for certain resources, dimensional constraints for positioning items and strength of friendship level requirement to enable certain actions within a social-network aware interactive narrative setting.

Who will benefit from this research?

Healthcare Providers
To demonstrate impact of the current proposal, we propose the creation of a prototype software system for learning transition constraints in real-world instances of nurse rostering problems. We will coordinate with Teesside University's School of Health and external stakeholders, to acquire real-world rosters from hospital wards.

Healthcare Informatics
Healthcare rostering is part of the wider field of Healthcare Informatics. Academic output relevant to the impact case will be disseminated at relevant Healthcare Informatics venues, such as AIME, AMIA and IEEE ICHI.

How will they benefit from my research?

Healthcare providers have to operate in a rapidly changing regulatory and legislative environment. As an example, the National Institute for Health and Care Excellence (NICE) has recently issued detailed new requirements for the safe staffing of hospital wards following problems with staffing levels at Mid Staffordshire NHS Trust. Providers operate in an environment where they must provide adequate staffing levels, on limited budgets, and within legislative boundaries (for example, the European Working Time Directive).

We will release all software that contributes to the academic work packages as open-source software. In addition to this, by the end of the work programme, and through discussion with our stakeholder group, we will be in a position to further develop the prototype employee allocation system into a commercial product.

Two ways of commercialising the output from the impact packages are relevant to different types of end-user. For larger organisations, a product to be used off-the-shelf that would compete eventually with systems such as Allocate Software's HealthRoster could be developed. Learning the constraints, rather than programming them explicitly, provides a competitive advantage in the speed to deploy software when new constraints are added to the system. In addition, constraints will be learnt automatically in real-time, from the vast data accumulated by healthcare organisations.

For smaller healthcare providers with less resources to invest in large systems, a web service will be set up where users can manually input their current rosters, and the constraints on their staffing will be inferred. This could be provided at a lower cost, or potentially free of cost, and still provides significant societal impact.

Successful deployment of these software systems can lead to cost savings along with higher staff and patient satisfaction.