Our hectic, on-demand lifestyles rely upon allocating finite sets of resources to constantly changing numbers of people. As this task grows ever harder, it will require solutions to a little-known mathematical riddle.
By Gemma Church
It’s not easy to accurately predict what humans want and when they will want it. We’re demanding creatures, expecting the world to deliver speedy solutions to our increasingly complex and diverse modern-day problems.Over the last few decades, researchers have developed a range of pretty effective mathematical solutions that can allocate resources across a variety of industries and scenarios so they can attempt to keep up with the daily demands our lives place on them. But when an allocation made at one time affects subsequent allocations, the problem becomes dynamic, and the passing of time must be considered as part of the equation. This throws a mathematical spanner in the works, requiring these solutions to now take into account the changing and uncertain nature of the real world.
Such problems are collectively known as dynamic resource allocation problems. They crop up anywhere you find a limited resource that needs to be assigned in real time.Whether you’re waiting for a taxi or a next-day delivery, the list of dynamic resource allocation problems and their everyday applications is “almost endless” according to Warren Powell, an engineer at Princeton University who has been investigating these problems since the 1980s.
But dynamic resource allocation problems are not just concerned with giving humans what they want, when they want it. They will also be essential for tackling some of the world’s most fundamental and complex issues, including climate change, as they help us allocate our planet’s often scarce and depleted resources in the most efficient ways possible.But let’s first look at a simplified example to see what a dynamic resource allocation problem is and what makes it so difficult to solve.
Imagine you’re cooking a roast dinner for your family of four. You opt for beef with all the trimmings, safe in the knowledge that it’s a firm family favourite. But just as you’re about to serve up, your daughter announces she’s vegetarian, your partner texts to say they’re running late, and your son tells you he’s invited “a few” friends over for dinner too. Then, your dog runs off with the joint of beef while you’re desperately trying to work out how you are going to meet the needs of all these (quite frankly) very demanding and unruly individuals.They will be essential for tackling some of the world’s most fundamental and complex issues, including climate change
This is a trivial example of a dynamic resource allocation problem, but it demonstrates some of the core challenges researchers face when tackling these problems. For starters, the parameters affecting demand change unexpectedly both in the short and long term. There’s no way you could have ccurately predicted your daughter’s new dietary requirements, your partner’s tardy arrival or your son’s additional guests as you were prepping this meal.
In the longer term, demand for meals in your house also changes on a day-to-day basis. You may need to feed two or 20 people at each sitting. From meal to meal, you have no idea who’ll want feeding, what they will want or when they will want it. You can take an educated guess based on prior experience, but this is not a robust method because human nature and the many other parameters affecting demand are unpredictable.
The actions of the individuals in this scenario also affect the future state of the system. Every time you allocate a specific meal to a person, this changes the system. It removes both one hungry person and food from your kitchen.
“All [dynamic resource allocation] examples need to deal with changing inputs and environments, which are highly dynamic and difficult to estimate and predict, as the future load is not statistically dependent on the current load,” says Eiko Yoneki, a senior researcher leading the data centric systems group at the University of Cambridge’s Computer Laboratory. “One change triggers another change, and if you want to control the system with accurate decisions, one must consider the future status of the system.”
What’s more, as more people or meal options come into your kitchen, things are complicated further. You now have more ways to allocate a range of different meals to different people. This number of combinations scales exponentially as you add more people or meals to the system.
This is exactly what a large hospital may face, for example, when trying to feed all the patients coming through its doors. The same applies when trying to treat these patients. The medicines they require, which themselves have a limited shelf life, and the equipment needed for diagnosis and treatment will change constantly as different patients arrive. Limited resources like MRI scanners, doctors and nurses need to be allocated too. To address this, and prevent costs from soaring out of control, the hospital management might deploy mathematical models to help coordinate all these things.
The trouble is that most existing methods rely on historical data to make predictions. This method doesn’t scale very well for such systems and can’t cope with even the smallest changes. If a change does occur, they go back to square one and start working out a solution all over again. Such problems quickly become computationally intractable, even for a fairly small number of people and resources – whether that’s a meal or an MRI scanner.
Dynamic resource allocation problems also arise from a range of different scenarios and each one has its own specific issues. For example, Yoneki is investigating the implications of these problems to help our computer systems and applications run faster and more efficiently.
“Modern computer systems are complex, and many configuration parameters need to be tuned, including resource allocation such as memory, computation capacity, communication capability, and any input to the systems,” she says. “Computer systems are dynamic and deal with ever-changing environments, which requires dynamic control methodology.”
Mobile phone networks and cloud computing are reliant upon solving these problems too
So, the computer you are reading this article on is almost certainly wrestling with some dynamic resource allocation issues at this very moment. Mobile phone networks and cloud computing are reliant upon solving these problems too.
Delivery firms are also tackling dynamic resource allocation problems to speed up deliveries. For example, UPS developed its On-Road Integrated Optimisation and Navigation (Orion) system to optimise its delivery routes using advanced algorithms. The company claims the solution has saved it 100 million miles per year – but other reports reveal the system struggles in complex urban environments.
Supply chains are another “problem that is never going to go away”, says Powell, because of the complex nature of today’s products. For example, if you want to manufacture a standard smartphone you need to coordinate hundreds of components from around the globe, all of which are brought together in a specific order on the factory floor. “Supply chain disruptions are a major problem when trying to meet the needs of society,” he adds.
Our energy supplies are also increasingly complex, relying on unpredictable renewables such as wind and solar. The outputs of these sources can fluctuate wildly, as can demand for energy at any given time. The cost of energy can fluctuate too – electricity prices can spike up to 50 times their average within a five-minute period.
In truth, you will struggle to find an industry that doesn’t faces the challenges of managing a dynamic resource allocation problem in one form or another. “Electricity prices, yield of parts in a supply chain, travel times, equipment failures, and the behaviour of people are all issues I have had to deal with,” says Powell. “This problem is so rich that there are at least 15 distinct research communities working on this problem from different perspectives.”
This is an important point. The diversity of dynamic resource allocation problems means there needs to be industry-wide standardisation of the different computational techniques and methods used to tackle it. Powell is one of those attempting to bring together the disparate communities working on dynamic resource allocation problems. “Our approach does not replace any prior work,” he says. “Rather, it brings all of this work together and helps to identify opportunities for cross-fertilisation.”
Advances in machine learning are offering new hopes of tackling dynamic resource allocation problems
A rich set of operational management tools have been highly effective over the last few decades to address dynamic resource allocation problems, helping the world’s airlines, logistics firms and road networks increase their performance in a range of ways. However, “high dimensionality” – where many different parametres need to be taken into account – and uncertainty “remains a challenge”, according to Powell.
Advances in machine learning are offering new hopes of tackling dynamic resource allocation problems. An artificial intelligence technique called deep reinforcement learning allows an algorithm to learn what to do by interacting with the environment. The algorithm is designed to learn without human intervention by being rewarded for performing correctly and penalised for performing incorrectly. By attempting to maximise rewards and minimise penalties, it can quickly reach an optimal state.
Deep reinforcement learning recently enabled the AlphaGo program from Google’s DeepMind to defeat the world champion in Go. The system started off knowing nothing about the game of Go, then played against itself to train and optimise its performance. While games are an important proof of concept for deep reinforcement learning techniques, learning how to play games is not the end goal for such methods.
Yoneki and her team have been working on providing a viable alternative to human-generated heuristics for performance tuning in computer systems using deep reinforcement learning. The computer system they have been developing can scale to solve decision-making problems that were previously computationally intractable. It addresses the issue of computational complexity and can also respond to changing parameters in real time.
Systems employing this approach have already been used to optimise system performance in areas including resource management, device payment optimisation and data centre cooling. “Such applications are just at the beginning and open up a whole new world of opportunities,” says Yoneki.
A team of researchers at an artificial intelligence startup called Prowler.io, based in Cambridge in the UK, is also using its own machine learning approach to tackle dynamic resource allocation problems. Its algorithms provide incentives to induce a specific behaviour in the system. In a real-world context, this could be equivalent to introducing smart tolls to incentivise drivers to use specific roads and minimise traffic congestion and pollution.
As our populations continue to grow and our hunger for on-demand services increases, the complexity of dynamic resource allocation problems will only intensify
But there is still much work to be done in the machine learning field, says Yoneki.
“Use of reinforcement learning will move dynamic resource allocation problems forward, but it requires a lot of data to build a reinforcement learning model, and it is still at an experimental stage, especially computer systems where more complex parameters have to be dealt with than simple game cases,” she says. “The research on this topic is rapidly progressing.”
We’re still some way off cracking this unique set of problems as today’s techniques and computational resources quickly run out of steam when we try to tackle the complexity and random nature of the real world. But as our populations continue to grow and our hunger for on-demand services increases, the complexity of dynamic resource allocation problems and their impact on our day-to-day lives will only intensify.
And if we don’t start to address dynamic resource allocation problems now, we won't just struggle to get dinner on the table – the entire world could grind to a halt.
