AI on Spring I love it when an OptaPlan comes together - Geoffrey De Smet @ Spring I/O Bridge

so hi guys I'm going to talk to you about artificial intelligence on spring and more specifically planning optimization which is a subsection of artificial intelligence now planning optimization is probably one of the most profitable or impactful things we can do with AI and well it doesn't belong to the neural net side it's not things where it's not pattern recognition voice recognition or image recognition but it is still very much AI and I'm going to show you to that today so and I'm not related to Hannibal J Smith but I do love it when a plan comes together right so here's the application I'll be building for you today so basically it's a simple timetabling application just to give you an idea on how you can build your own planning application and in that will be assigning lessons like the English / the chemistry lesson and the Matt last as you can see here - time slots such as Monday at 8:30 and two rooms such as room a and room B and so forth and when you have a solve button there and that's when the green button there that's when the 8i algorithms do their work now just give you an idea on what's the input and the output of the application ability that I'll be writing you for you today so we have a number of lessons as you can see here again for lessons you have a number of rooms sometimes we have some slots where we can put those four lessons in and we have a number of constraints so other constraints there are things we cannot do in our playing so for example you can only put one lesson in one room at one time at the same time so we cannot say math and chemistry let's both put them in the room a at the same time right other constraints are for example when two lessons share the same group of students like math and chemistry they are both shared by the ninth grade we cannot put them in the same time slot you can so you need to make sure that these two lessons the green and yellow one do not occur at the same time same for the French and history lesson they are both followed by ten grades let's presume there's only one 10th grade class here it's a very simple case we want to make sure that those don't occur at the same time now as you can see chemistry and are attended by different student groups but they are attended by their thoughts by the same teacher by Marie Curie so we want to make sure that chemistry and French also do not occur at the same time so what we're going to do is with our spring with applications we're going to give this to the panel and op the planner will give us a solution and this might be for example solution as you can see the ninth grade doesn't have two lessons at the same time the 10th grade doesn't either and Marie can also do both of her lessons without splitting herself in two right so that's what we're going for that's the that's the case we're going to solve today now the interesting thing is this is just one planning problem right and what you'll learn here will apply to many other planning problems too and that's it the thing to keep in mind during this session so for example you can do equipment scheduling with it so it's the scheduling of hospital beds or cat scanners or rental cars so anything that is reserved for a number of days and you want to make sure that you want to increase your utilization by scheduling that equipment as efficiently as possible another planning problem you might have and you can solve it but what you learned today is for example job shop scheduling in where you have an assembly line where you're building cars our books or furniture and you want to reduce the makespan the amount of time it takes to actually build those things now the interesting thing about that is that when you build a car with a sunroof you shouldn't have three cars that need a sunroof all after each other on the on the car belt but on the other hand you have constraints like when they're you need to paint the car red you want to have as many red cars after each other on the assembly line so again those constraints play into play into account to make it more difficult to reduce that makes men now one of the or actually the most interesting case I would argue is the vehicle routeing case in which we need to deliver or visit a number of locations across the country and we want to do that as efficiently as possible so for example the yellow vehicle over here stops at these these dots as you can see the purple one stops and those dots now this applies to last mile delivery or or any kind of transportation cases but it also applies to technicians on the road for example to install telco at people's homes or to fix people's dishwashers and stuff like that right and the interesting thing is when you do this we have actually apply this then in some some cases up to ten of the multiple tens of thousands of vehicles and we wat besides we saw a reduction of driving time of twenty five percent 25 percent reduction of driving time for a fleet of ten thousands of vehicles translates into hundreds of millions of dollars per year savings it also translates into tens of millions of kilogram of co2 in maybe reductions of due to the fuel emissions so it's good for the environment and it's good financially right so there's great potential in that one then another one is bin packing for example assigning processes on the cloud as efficiently as possible to increase again utilization of these machines and one of my favorite favorites is employee rostering where we're trying to increase the health and the happiness of the employees by making sure that their that when we assign them shifts for example nurses or doctors or or security guards and so forth we make sure that when they want a free day that they get that free day right when they don't like to work afternoon so we try to give them more mornings and please like that but also take into account all labor regulations health regulations for example but they have enough sleep between two shifts and things like that which this gets really interesting lately of course due to the global crisis and these actually add extra constraints for example certain shifts in certain hospitals should not be given when for example in a Cove it wort to people who have a high risk of when they get Cove it for example based on their corporate comorbidities or age or things like or any function of that and of course the interesting thing is we docked opener we can add or we can add such constraints right so I was going to try to build an application so normally I build an application from scratch given the time limits this this is a more TL DR so she says good thing of course going to fast forward a little bit and I'm going to show you what I've already built and I'm going to continue on that adding in optical on the existing spring boot application so I have a spring boot application and in the spring boot application I add spring wet web web together to expose a rest service I added a simple JavaScript UI we shall see in a minute which is to show those which already saw screech at a friend and I'm communicating through that rotation plain old Jackson and of course I'm using spring that ought to go to relational database to hibernate to store that into an h2 in-memory database right so this is what's there already and I'm just going to show you that right now so there's no no AI in there whatsoever yet so let's take a look what we have here so I generated this which start of spring dot IO I have the typical dependencies but as I told you the data JPA to go to the database and I'm exposing all the rest repositories automatically but all the data repository is automatically true rest interfaces and h2 at runtime besides that I have a few more Java scripts for the UI a couple of web jars to make the UI pretty but that's not important as we only care about the back end today okay so what do I do have in here let's take a look so we have the spring booth application the typical one with spring boot annotation over there I'm going to add some test data as you can see here a couple of times lots I'll go into the templates in a minute but I'm adding ten times that's the three rooms in a bunch of lessons right so let's take a look at the domain alright and this is of course a crucial part understand what's the domain what's what we're going to solve so we have a time slot which has a day of week like Monday Tuesday Wednesday and so forth which has a start time for example 9:30 and which has an end time for example temporary right so that's its time tilt and that's during that time we can do one or more lessons as long as they're not in the same room of course right then we have a rule we're going to keep it simple it simply has a name room a room B room C and so forth on top of that of course we have the lesson and what is a lesson it is giggle ensues as mad French chemistry right the teacher such as Alan Turing Marie Curie and so forth and a group of students such as the nine greater than great and so forth as if you can see never keep it very simple here I've just used strings to represent those three things but of course in a more elaborate example you'd actually have subject class a teacher class and so forth okay these lessons need to be signed to a time slot and two rooms each lesson has one time slots and has one room or we'll end up with one time soft and one room because when we start out before we use our AI algorithms they will not be assigned and we'll use the opt open area it's actually make sure that those get assigned the other way around of course a room can have multiple lessons just not at the same time just one after each other right so that's a one-to-many relationship for a minute you want depending on how you look at it okay let's take a look at that in the code so in the code we have our room class of course some annotations here to put it into the database I'm going to ignore this for now right the string name that's the most important thing here the ID for the database again then a couple of constructors and then to string and some getters and setters to make it all usable of course you could do this in Kirkland 2 and this would be less code I personally prefer while I'm more comfortable on the average on Java today so I'm going to go to a time slot and a time slot same thing some annotations for JPA to put it in the database and the ID and then the three things that matter the day of week which is of course Java time you should only be using Java time when you leave the time and Java util date and of course start time and end time again a local time here more elaborate examples this might be an offset time or a zone time but this one will just presume that everything is happening in one time zone okay then the most interesting part is of course the lesson in the lesson we have our subjects our teacher and our student group and strings and we will need to assign them to a time soft inner loop so you can see when we create the test out of it they constrict this constructor over here they get assigned to a subject and to a teacher into a student group but there is no temperature in the room so those will and will start up as n your level right so now we need to be able to bring all of this to the UI of course and because we have multiple lessons multiple rooms and multiple times we need to have a wrapper object and that's actually the time table right so this is the one jason object we send from the back end to the front end and it has a list of all the times of a list of all the rooms and a list of all the lessons and again some getters and setters and then some extra constructors there so let's take a look at how that looks on the UI side I'm going to go to localhost here oh yeah I'll better first start running it so let me open my turn now let me just to run it spring boot up here alright so and well let's starts up I'm exposing this time table to a time table controller which for now is simple listening to the time table and create and gives us the time table right and so that's the time table repository I'm sure that is you show that there's a fine method so in this Fineman we were doing what we're doing is we're taking all the time slots all of the rooms and all of the lessons from our repositories plain old simple spring repositories were collecting these all into time table objects so that doesn't actually exist in the database a time table object and we're sending that back so this is transactional and we're sending that back to the controller who's sending it back to the UI on on this rest URL okay like I said the repositories are pretty simple typical paging and sorting repository and the final metals that I've added so I can use it in the time table for three okay let's take a look at what that gives us on the front end so if you do if refresh here you can see we have the unassigned lessons at the top bottom those are all those I added in the spring booth application let me just show you here so those are all the ones that I added here right in the during the command line runner to add a demo data right such as chemistry math biology you can see those over here to chemistry to hear and so forth and of course we have our rooms and our time slots and now just one simple thing left to do is pick which time slot which lesson goes into which of these cells right and it's actually not as simple as you might think I'll show that in a minute but okay let's press the solve button what do we get the solve is not yet implemented why not because when we go back here go back to our controller and then just show this a little bit when we hit that end point there's a throne Owen unsupported operation exception right so this is the part that we now need to start implementing so it's time to start coding and that's add that okay so what I'm going to do is just reach back to my slides I'm going to add this application and simply add the OP to plan our spring boots starter in there and let's do that right now so I'm going to go to the pump file I'm using maven today of course you can do this with Gradle too yeah this is of course this saw that we called nothing special in that stack trees there and I'm but I'm going to do this here in the spring boot starters I'm simply going to add maybe over here dependency I'm going to use springing boot starter here we go and I'm going to use the latest fresh right so simply adding the under spring good starter this is intelligence so I'm just going to import the things and I should now have access to everything in there so the next thing we need to do is we need to tell opto planner what it can change for us so if you go back to our slides remember this is our domain objects right remember our lessons need to be signed two times or 10 a room so these are the things that start out as annular well we need to tell opt opener that it cannot change the subject or teacher well we just need to tell them what it can change so we need to tell optimal here those orange things the time slots and the room those are the things you can change those are planning variables those are variable during planning during solve right and because of these these two properties they are in the lesson class then the lesson class needs a planning entity annotation that's basically a way of saying there's some planning variables in this class please pick those up and users okay so the time for the room field starts none no before we solve it then we give it to opt opener when it comes back these time shots and these rooms will be assigned now it's just not one lesson that he's being that's being assigned with all of the 20 25 or 30 lessons we have in this case and it's going to make sure that they're assigned such that they are in not in conflict with any of the other lessons right so that's that's the difficult part right okay so let's take a look at actually doing that so we're going to go to the lesson class as I mentioned earlier we need to have had planning entity over here so now up to tower knows there's something in here that I can change and now we need to tell them what exactly he can change well that's the time something of course so we're going to say this is a planning variable you can now change that now one of the things is of the player needs to know okay I can change the time looks but which time shots can I put in there right let's say I have a couple of lessons I take for the first lesson the math lesson where which that can I create time shoots out of the blue no that's not true you need to take pick one of the functions that's available like for example monday a 30 so we need to give him a list of collection or a range of tangents so and this is called a value range and in this way the refs I'm going to say I need you to take the types of range and somewhere else we're going to actually hook in this ID where we have the actual list of times I'll show you that in a minute same thing for room this can change during planning so it's something that octopi needs design for us and in the same case we'll have to give them a list of all rooms so let me just call this the room range okay that looks fine so that now what the parent can actually start assigning those but it needs to it can it it cannot solve this too unless it needs to get all of the lessons in one package right it needs to solve one problem and that's a time table so that's basically that's the planning problem that the player will solve with Q because here all it has all the lessons and when it solves it when it returns it will returned again a timetable which contains for example all of the lessons right and you might actually have multiple planning entity classes and in which case and this becomes a bit more complex but anyway so this is something that will also be a solution once it's solved so I'm going to prop the planner to know that this is basically our data set right because you know and this is a solution once we solve it it's called the planning solution you'll actually see multiple of these because of pitar you'll find better and better solutions and we'll give them back as time table instances for you so it needs to know here's that property that contains all my planning at you or at least here's one of those properties we just need to say this is a planning and the collection property right and then now up to par knows when he gets a time stable here I can find all my lessons and I can start assigning these now the problem of course is we need to give them all of the time a list of all the time slots to pick from that's so that's this actually this types of lists already seem to have it already so let's just add that this is a value range provider and I'm going to just call it so the ID is that time slips arranged right similar for the room range I'm going to just say this is the room range okay looks good one more thing once we solve this fit of the planner it's opt opener will actually give this a grade score to tell you how good to this solution is and he wants to actually add it into the planning solution so I'm going to add a score here this is a hard soft score which means it will tell us how many times your hard constraint is broken and how many times your soft constraint is broken of course we're going to try to get the best possible score again for up to thunder to pick this up you want to add the planning score annotation there okay this looks good let's actually hook this up into our controller so when we have the souls method here we need to now call something to solve so op the planner can add for this spring boots starter kanaky auto wire a solver manager for us so solver manager is like an entity manager but then for soul pay I sold a planning problems and it's it is generic so I can say I'm going to give it a timetable and we'll solve that for me so this is our solver manager and more and more specifically it can handle multiple tenants and those can have a job ID so that's the dual I'm going to use long as job at least you might want to use your IDs that works too so what I'm going to do here is I'm going to say when you call the source methods I am going to solve and listen so what does that mean I'm going to solve a problem right and when that problem is every time we find a new better solution to that problem and a solution where you have a higher score right we're going to store that into the database so we can actually see the progress up the planner finds better and better solutions and we can show that into the UI the first thing I need here I need to give it a job ID so I'm going to keep that simple just one just one now I need to give them a function where I can load the data sets right so I'm just going to load the data set directly from the time table repository I'm going to use the finder so given a job ID like a problem idea right word I'm going to say here just find that now the last thing when I actually find a new better solution I'm going to need this or store that so I'm going to say the time table solution please save that into the database so I'm going to and here I can just directly wire in that so let's take a look there so when we go into the save method what actually will happen is it will take the time table we'll go through all of the lessons and save those lessons right so as op the planner assign both of time slots and the room actually save it into the database which will allow our UI which is just pulling to actually show that results one more thing we need to do is we need to add a constraint provider that's actually telling in them what up to plan needs know what is better and what is worse so for now I'm just going to throw in a dummy one and call it the time table constraint provider all right I'm going to implement constraint provider and I'm just going to do that dummy dummy wise and we return a new constraints right no constraints so far and just moments right okay so let's take a look when you happens when we run this so you can just to rerun our application let's see if that actually boots up if you don't get any exceptions if there's something wrong of the parole fail first for example if I'm misspelled room range or something like that but nothing went wrong so we can now solve this you can now go over here and refresh you can create this all but let's see if opener starts actually signing those lessons remember we don't have any constraints so far we've not said what it cannot do so when we do this what happens op the player assigns all of the lessons into the first room into this first time so we're bei you know it's this is not a feasible schedule right this is breaking a lot of hard constraints namely that all of the lessons you know are in the same room at the same time so let's fix that let's go back to our constraints over here and let's actually add a room conflict because constraint so we're going to add a room conflict constraint the constraint factory here just add that method right now you could write it with a bunch of for loops but I'm going to use the technique which is far more scalable because it does incremental calculation and it's an API it's very similar to SQL so I think SQL when you read this right so what I'm going to do is I'm going to say I'm going to select a lesson right and when I then join that with another lesson so I have two lessons which are in the same room at the same time then I'm going to penalize that as a room conflict and this is a heart something that really should never happen so it's a hard score so I'm going to add this as a heart soft scone if it's something that can has allowed to happen but we want to minimize that we would say one soft right now you know just to any two lessons we need to actually have two lessons are in the same room at the same time so we need to say okay these are I mean to join them on equality and we need to say these are two lessons that are in the same time slot right and also they are at the same time in the same room right so good lessons in the same room at the same time right okay let's take a look what that gives for us let's run that okay you run that we switch back to over here we refresh we wait a few seconds for the server to start up here we go just one more here we go and we click the solve button and what happened now now all of the lessons are assigned to their own room in their own time so we don't have any room conflicts anymore and this is pretty simple to do as a human yourself right you could easily do this yourself and just pick one and put one on each time shot however this is not a feasible schedule because if you look at it from the teachers point of view we're asking Alan Turing to be in two room to teach two lessons at the same time right the ninth and the tenth grade and same room at the same time so that's a bad idea right so let's go back to our code let's figure this like two so I'm just going to duplicate the other one I'm just going to say I'm gonna have a teacher conflict right when I have and I'm just going to duplicate this constraint here say this is now a teacher conflict and I'm going to say okay when we have two lessons and the same timeslot and the same teacher then we were asking a teacher to be in two places at the same time and of course that's a bad idea we don't want that notice the top these two constraints are isolated from each other so if we enable or disable one or we refractories across when we have dozens of these kinds of constraints we can just focus on one at a time and it's really nice of course right okay let's take a look what that gives us let's take the solve button we can see we have them very room we look at per teacher we can see we're not asking a teacher to be in two places at the same time however when we look at the student groups were asking certain student groups to be in two places at the same time so same logic we again go back this is getting a bit repetitive of course but we're saying okay before it's too group I want to make sure that when I have a group of students that if they have two lessons at the same time that that it's not that we cannot allow that so in here of course we say equality on the student group and these are all hard constraints right now let's go back for a second this refreshes I can see that you now press the solve button that the algorithm automatically adjusted itself so here again all of the rules you only have one lesson in one room at the same time we have this is the teachers view right no teacher has to be in two places at the same time and same for your students now coming up with this schedule as a human is already quite difficult it's exactly already quite difficult but and it's a feasible schedule something you can actually put into production however it's not a great schedule so if I had more time I'll actually show you but what we can easily do is we can add these math we can for example ask top laner to not have these gap hours and then it would automatically push those lessons together right so that would be a soft constraint basically telling for the sake of these teachers make sure that when they have to come to school they don't lose any hours in between lessons right it's just one big chunk of lessons in one time or even avoid spreading it across two days and stuff like that and and of course the planner would automatically adjust to that even one and one interesting one I've actually seen these days so when we talk so talking hard and soft constraints or hard constraints must not be broken soft constraint should avoid being broken another one is when in in this Cove is 19 Hara is when you want to do school timetabling and we want to make sure that the teacher the students in the class in the room in the hallways flow from left to right so flow from room to room B to room C but never go from room C to room a unless there is a break in between and that's pretty easy constraint to add to so let me just quickly show this one and this constraint so that you can actually see that it's if you look at the solution now it's being violated so look here the ninth grade is going from room B to room a at the 9:30 and there's no break between there so if we go back to our constraints here we throw in this constraints I'm going to not explain it now to to just to go for to do this quickly and you will now see that if we refresh this right and remember we saw our nine grades in our previous solution going from room B to room a at the 9:30 segue and we can now see that it's no longer happening in fact apparently it's putting all of the lessons in the same room right now it's keeping it simple once we added more of the other stuff constraints that won't be a good possibility anymore because you can still see for the teachers are still a lot of gaps right but we can have our cake and eat it too we can have add both of those constraints both as soft and they will be rated against each other and based on that of the world will find the a win-win situation for everybody so if there's any questions on the score will happily answer them all right well thank you very much you're free so we have a couple of questions here the first one haze' what is the range of algorithms that up the plan uses the user is saying I solve that time type of generation problem for a faculty with my own genetic algorithm yeah so up the flowers using I can show you that up the player is using the bunch of local search algorithms such as stop with search simulating and so forth I have a good overview here in optimization algorithms so these are the ones we have implemented of course brute force branch and bounds those don't scale they're not really that useful which of conscription ristic they get a greedy easy quick solution quickly such as first fit first with decreasing cheapest insertion and stuff like that and then a bunch of metaheuristics such as local searches that we search similar needing a late acceptance actually that we search and latex late acceptance those auto and and symbol leading at times are really the best of the best algorithms we have a bunch of others too we've done a bunch of experience with genetic algorithms and I'm following up the research chair as well as the economic challenges around that genetic algorithms sound cool they have a really cool way of doing things there they're not performing in reality against the others as far as I'm following the research and forum and seeing for these kinds of cases genetic albums do have appliances on other kinds of cases before which you know which fall out of this typical planning problems right so right use the right tool for the right job for example some people are trying machine learning algorithms on this more critically neural nets on this on these kinds of use cases they well for they reduce the driving time by one to two percent instead of twenty five percent so they to get some results but they're they're definitely you know they should stick stick to image recognition and voice recognition all those wonderful things the right tool for the right job don't use a screw driver on the nail don't use a hammer on a on the screw right thank you another question is it possible to modify constraints in in at one time you could just go through you could just create a new solver factory so you could do that well there's a couple of approaches so first of all if you're talking about changing the weights of the constraints or the data in the constraints yes we do that all the time so I don't I can spit late to start the example now but one of the things we can actually do is we can we can say for each of those constraints we have there we can for example the kovat constraints we could disable that and we can disable the based upon something that's in the time table so in the time table we can say we want to dacovia constraints on or off and we want if it's all we wanted to have it you know a great importance or low importance and you can have to you the user in the UI actually play with those weights and those settings and those constraints and turn them on and off more furthermore many of the constraints you can declare generally so for example instead of saying a nurse can for a free day off on Friday you can say a nurse can ask for any time off on any day for any period of length and so you can make it very very general and that that already allows you to do many constraints however very specific new constraints to turn you can just reboot to the solar factory but that's a little bit more expensive okay and just the last one real quick some attendees are confused on where those Optima at a planner run does it run locally in the cloud the planner it's an embedded java gr so you run it wherever you want to run it where Java runs but of course it's it likes being run on the cloud right because by default up the planner just uses one thread one core just to make sure it's easy for during development so it doesn't eat your entire system which you can actually give it more threads and then it will do multi thread solving and I kind of like call that donating threads because octo planner likes one thing and one thing only that's I that's CPU power right so there's no i/o memory wise it's very low but it will eat every millisecond of CPU you give it so if you give it more threads then you have CPU cores you will see that on your system you will not be sharing with zoom or something at the same time all right great thank you for your presentation people really enjoy that are there a couple of questions more on the disk or channel so if you can jump into this course channel that would be great all right and well we'll just do just two minutes of break because now we're going to go for the first quiz so get ready for the quiz right then I will be back in a couple of minutes

Channel: Spring I/O

Views: 3,293

Rating: 5 out of 5

Keywords: springio, springiobridge, Spring Boot, OptaPlanner, AI

Id: moiSzzy5ba0

Length: 35min 10sec (2110 seconds)

Published: Tue Jun 02 2020