Reinforcement learning applicable to a scheduling problem? - Artificial Intelligence Stack Exchange most recent 30 from ai.stackexchange.com 2022-01-27T23:05:34Z https://ai.stackexchange.com/feeds/question/28888 https://creativecommons.org/licenses/by-sa/4.0/rdf https://ai.stackexchange.com/q/28888 2 Reinforcement learning applicable to a scheduling problem? PeterBe https://ai.stackexchange.com/users/48758 2021-07-28T14:34:06Z 2021-08-05T09:43:30Z <p>I have a certain scheduling problem and I would like to know in general whether I can use Reinforcement learning (and if so what kind of RL) to solve it. Basically my problem is a mixed-integer linear optimization problem. I have a building with an electric heating device that converts electricity into heat. So the action vector (decision variable) is <span class="math-container">$x(t)$</span> which quantifies the electrical power of the heating device. The device has to take one decision for every minute of the day (so in total there are <span class="math-container">$24$</span> hours <span class="math-container">$\times 60$</span> minutes <span class="math-container">$= 1440$</span> variables). Each of those variables is a continuous variable and can have any value between <span class="math-container">$0$</span> and <span class="math-container">$2000 W$</span>.</p> <p>The state space contains several continuous variables:</p> <ul> <li>External varying electricity price per minute: Between <span class="math-container">$0$</span> Cents and <span class="math-container">$100$</span> Cents per kWh (amount of energy)</li> <li>Internal temperature of the building: Basically between every possible value but there is a constraint to have the temperature between <span class="math-container">$20 °C$</span> and <span class="math-container">$22 °C$</span></li> <li>Heat demand of the building: Any value between <span class="math-container">$0 W$</span> and <span class="math-container">$10.000 W$</span></li> <li>Varying &quot;efficiency&quot; of the electrical heating device between <span class="math-container">$1$</span> and <span class="math-container">$4$</span> (depending on the external outside temperature)</li> </ul> <p>The goal is to minimize the electricity costs (under a flexible electricity tariff) and to not violate the temperature constraint of the building. As stated before, this problem can be solved by mathematical optimization (mixed-integer linear program). But I would like to know if you can solve this also with reinforcement learning? As I am new to reinforcement learning I would not know how to do this. And I have some concerns about this.</p> <p>Here I have a very large state space with continuous values. So I can't build a comprehensive <span class="math-container">$Q-$</span>table as there are to many values. Further, I am not sure whether the problem is a dynamic programming problem (as most/all?) of the reinforcement problems. From an optimization point of view it is a mixed-integer linear problem.</p> <p>Can anyone tell me if and how I could solve this by using RL? If it is possible I would like to know which type of RL method is suitable for this. Maybe Deep-Q-Learning but also some Monte-Carlo policy iteration or SARSA? Shall I use model-free or model-based RL for this?</p> <p><strong>Reminder</strong>: Does nobody know whether and how I can use reinforcement learning for this problem? I'd highly appreciate every comment.</p> <p>Can nobody give me some more information on my issue? I'll highly appreciate every comment and would be quite thankful for more insights and your help.</p> https://ai.stackexchange.com/questions/28888/-/30015#30015 2 Answer by Neil Slater for Reinforcement learning applicable to a scheduling problem? Neil Slater https://ai.stackexchange.com/users/1847 2021-08-04T12:28:57Z 2021-08-05T09:43:30Z <p>Details matter, and it is possible that your problem is best solved using classic control (solving the state equations) or operations research style optimisation. However, RL is also a good choice because it can be made to learn a controller that is not brittle when things go wrong.</p> <p>One thing you will have to accept with RL is that the constraints will be soft constraints, even if you penalise them heavily. That is, you can expect that the internal temperature could drift outside of bounds. It definitely will during learning. A major design concern when framing the problem for reinforcement learning is how to weight the different rewards that represent your goals. You can weight your strict constraints higher, but at least initially they need to be low enough that the cost saving is not completely swamped.</p> <p>I would suggest that your worst constraint failure penalty is slightly larger than the highest possible electricity cost for a single time step. That would mean the agent is always incentivised to spend money if it has to, as opposed to break the constraints, whilst still being able to explore what happens when it does break the constraints without having to cope with predicting large numbers.</p> <p>There are lots of types of RL. Some are better at different kinds of problems. I would characterise your problem as you have described it as:</p> <ul> <li><p>Episodic - but only for convenience of describing the problem. In fact your agent with a 24 hour episode will be incentivised to allow internal temperature to drop at the end of the 24 hours to save money, when it does not care what might happen immediately afterwards. Depending on price of electricity at that point, it could well be more optimal to spend more. This may only be a small difference from truly optimal behaviour, but you might play to strong point of RL by re-framing the problem as a continuing one (where mixed-integer linear optimisation may be harder to frame).</p> </li> <li><p>Continuous state space, with low dimensionality.</p> <ul> <li>If prices are known in advance, you may want to augment the state space so that the agent knows how long it has at current price and whether the next price will be higher or lower. Alternatively, if they always follow the same time schedule, you could add the current time as a state variable. Either way, that allows the agent to take advantage of the temperature bounds. For instance, it could load up on cheap heating before a price hike, or allow the temperature to drop to minimum acceptable if cheaper electricity is about to become available.</li> </ul> </li> <li><p>Large, possibly continuous action space. You might want to consider approximating this to e.g. 21 actions (0 W, 100 W . . . 2000 W) as optimising this simpler variant will be easier to code (a DQN could do it), whilst it may not significantly affect optimality of any solution.</p> </li> </ul> <p>I don't think you could simplify your state space in order to use Q tables. So the DQN agent is probably the simplest that you could use here, provided you are willing to discretise the action space.</p> <p>If you don't want to discretise the action space, then you will want to use some form of policy gradient approach. This will include a policy network that takes current state as input and then output a distribution of power level choices - e.g. a mean and standard deviation for the power choice. In production use you may be able to set the standard deviation to zero and use the mean as the action choice. A method like A3C can be used to do train such an agent.</p> <p>I suggest that you discretise the actions and use a DQN-based agent to learn an approximate optimal policy for your environment. If that returns a promising result, you could either stop there or try to refine it further using continuous action space and A3C.</p> <p>Also, you will want to practice using DQN on a simpler problem before diving in to your main project. Two reasonable learning problems here might be <a href="https://gym.openai.com/envs/CartPole-v1/" rel="nofollow noreferrer">Cartpole-v1</a> and <a href="https://gym.openai.com/envs/LunarLander-v2/" rel="nofollow noreferrer">LunarLander-v2</a> which also has a <a href="https://gym.openai.com/envs/LunarLanderContinuous-v2/" rel="nofollow noreferrer">continuous actions variant</a>. Learning enough about setting up relevant RL methods to solve these toy problems should put you on a good footing to handle your more complex problem.</p> <p>Keras documentation includes an <a href="https://keras.io/examples/rl/deep_q_network_breakout/" rel="nofollow noreferrer">example DQN for Atari Breakout</a>, that you may be able to use as the basis for building your own code.</p>