My initial interest in AI planning comes from a promise I made to a friend years ago, which I was unable to keep. He was an amateur theater director, and he was complaining about the time and difficulty of building a rehearsal schedule, where constraints included
- actors available at different times
- rehearsal slots of different length
- scenes of different length
- scenes that contained varying combinations of actors
- a hard constraint that each scene be rehearsed at least once before the play opened (I think he actually said at least twice, ideally three times)
- a soft constraint that scenes would ideally be rehearsed in order
- the reluctant possibility that if it were impossible to have all the actors for a scene together for long enough, you could provide stand-ins to allow others to rehearse
As an over-ambitious junior programing student, I said I could build something that would do that! Unfortunately (although perhaps unsurprisingly), it turned out to be quite a bit more difficult than I had imagined, and I never got around to it. Last year, I started looking into the problem again and I did build a much simplified version for an unrelated scenario (given
x conference attendees who have expressed preferences from 1-
y for each of
y conference workshops held over
z timeslots, which attendees should go to which workshops?) but the Automated Theater Rehearsal Planner was still beyond me. In late January, as I poked through the list of uncompleted projects, I once again came across this one and decided to look seriously into it - as a professional programmer, surely this is something I can do! And in a serendipitous moment, while looking up resources on scheduling algorithms I discovered that
this course had begun a few days earlier, so I signed up for it and this is now an active project that I hope to get into a useful state this year.
Some background info on the problem for reference
To understand the general domain of scheduling, I started at the broadest relevant page,
http://en.wikipedia.org/wiki/Automated_planning_and_scheduling, and after looking through it selected these relevant links
-
http://en.wikipedia.org/wiki/Preference-based_planning, which is relevant because of the soft constraints listed, such as preferring to rehearse in order and have all actors in a scene together
-
http://en.wikipedia.org/wiki/Scheduling_(computing) (if one considers the director or the rehearsal space to be the resource being scheduled) which led to
http://en.wikipedia.org/wiki/Job_Shop_Scheduling and eventually on to
http://en.wikipedia.org/wiki/Genetic_algorithm_scheduling and finally to
http://en.wikipedia.org/wiki/Scheduling_(computing)#Scheduling_optimization_problems and to this flow shop scheduling demonstration app:
http://posh-wolf.herokuapp.com/ (although flow-shop appears more restricted than my problem).
Since it seemed likely that at least a broadly similar tool existed, I searched for free tools to try out in order to clarify what I needed to build exactly. (Or if perhaps it already existed). When searching for basic 'scheduling tools' or 'resource planning', the results tended to be about processes, such as scheduling a factory line and supplier logistics for organising delivery schedules - it may turn out that this is the same problem, but they don't quite seem to match. When I searched for 'rehearsals' (or similar), there were no specifically relevant results, however I found that there is a ton of software available for employee scheduling. Since it seemed that this should have significant overlap with the problem I'm looking at, it seemed worth installing a couple of the freeware options to check them out.
http://www.kappix.com/download.htm
http://www.simulation.co.uk/
I found that the basic issue with these tools is that employee scheduling operates on the assumption that you have a fixed number of slots to fill for each session, and are moving the people into the slots (and in the more complex tools, matching the people to the required tasks for each slot). For the rehearsals, I have a variable number of slots, based on how many people can attend, and I want to see which scenes (tasks) are relevant to the largest number of these people.
Now, for the Creative Challenge project in the class: I'm going to get my scheduler app into a user-friendly state and post it to the class.
