Title: Multi-agent exhaustive scheduling with pathfinding AI and constraint satisfaction
Authors: Noorul H. Ali (computer science and engineering), Dhwani Vora (production design),
Institutions
NHA: Indian Institute of Information Technology Vadodara, Gujarat, India
DV: Whistling Woods International, Mumbai, India
Correspondence: NHA: 201851078@iiitvadodara.ac.in, DV: dhwanivora755@gmail.com
Abstract
Introduction
Results
Discussion
Methods
References
Appendix
Filmmaking involves scheduling of shots across the entire shooting period, taking into account factors like actor schedules, and location permissions. We attempt to recognize the combinatorial explosion problem at the heart of this and interpret it as a pathfinding problem. Strategies like constraint satisfaction, greedy, depth-first search, breadth-first search and A* search are used to efficiently solve this problem. The final algorithm is used to create an AI that can schedule the shoot of an entire film in 30 seconds, as opposed to the incumbent practice of doing it manually, which takes at least a week. In practice, this allows filmmakers to focus on their art, while the mundane aspects are automated. This algorithm is also extensible to other scheduling tasks.
A. Current state of shoot scheduling
A 1-hour feature film may consist of 250 individual shots, spread over multiple locations. Currently, the scheduling of these shots across entire shooting period (say 2 months) is done manually, noting actor availability, location availability, equipment availability, and so on. This laborious task usually takes more than a week. We recognize the combinatorial problem at the core and try various approaches to solve it efficiently.
B. Problem formulation
B.(i) Combinatorial explosion
A shoot schedule is simply an arrangement of shots. This arrangement must satisfy all constraints and minimize usage of budget. Trying to find most efficient shoot schedule is thus a combinatorial explosion problem [1].
B.(ii) Interpreting problem as exhaustive pathfinding
A path that traverses all shots with minimum budget (cost) needs to be found. Constraint satisfaction can be done independent of this path, fixing certain shots at certain positions, after which a path can be found. Each shot is interpreted as a location in pathfinding problem.
B.(iii) Interpreting shot as location
Each shot consists of actors and equipment. For simplicity, only actors are taken into account (equipment follows same principle). A shot is interpreted as a set of actors, each actor being an independent element.
B.(iv) Interpreting distance in pathfinding problem
Distance governs the heuristic and is necessary to find efficient path. We interpret distance between shots using Hamming distance [2]. Since each shot is a set of actors, the distance is a function of the number of actors in one set but not the other, and vice versa (difference between sets).
B.(v) Assumptions
1. Actors are independent of each other.
2. Shoot is done sequentially, no shot is done in parallel.
3. Each actor has a fixed price per day.
4. Each location has a fixed price per day.
5. A calendar day can have 3 shots taken in it.
6. Actors are the source of most expense, hence optimizing schedule for actors’ time will lead to most efficient budgets. This was tested in dummy schedules with less than 20 actors; actors with high per-day costs were grouped together.
B.(vi) Goal
We wish to build an algorithm that generates an optimum shoot schedule in polynomial time.
Functions and variables
1. variable scene: Each scene is defined by its actors and location. Array of actors and location.
2. variable shootSchedule: Array of scenes and dates they are scheduled on
3. function totalExpense(shootSchedule): Cumulative cost of actors for given shoot schedule. Obtained by multiplying daily cost of each actor and days the actor is scheduled. This is the primary variable optimized to be minimum in an optimal film budget.
4. function minimumExpense(actor): Minimum cost per actor. Obtained by multiplying actor cost per scene and number of scenes they are in. Least possible cost for each actor. For simplicity, each actor is assumed to do 3 scenes per day, or actor cost per scene = actor cost per day / 3
5. function currentExpense(currentShootSchedule): Cumulative cost of all actors till current date of current shoot schedule, if remaining scenes are not shot
6. variable totalShots: Total number of scenes in the film
7. variable scheduledShots: Number of scenes already scheduled
8. variable percentShotsDone: scheduledShots / totalShots
9. function Hamming_distance(scene1, scene2): Metric for difference in actor compositions between 2 scenes. Returns 0 if 2 scenes have the same set of actors, otherwise returns Hamming distance.
Simple constraint satisfaction solution
The constrained nature of an optimal schedule led us to interpret this problem as a constraint satisfaction problem (CSP) [3]. Each node in this CSP is a scene with a list of actors in that scene. A film is a list of scenes. A particular day and time (out of 3 per day) could be assigned to each node (scene), with actor availabilities as constraints: the same actor could not be in the two shots at the same day and time. Actor availability and location availability were given as input. A shoot schedule was generated using simple constraint satisfaction, with each scene satisfying the actor and location constraints of its set of actors and the location it needed to be shot at. A shoot schedule was generated by assigning each node a number (function of day and time). Backtracking was also used.
Greedy pathfinding solution
This approach uses greedy pathfinding [4]. Initially, a random node (scene) is chosen. Subsequent nodes are chosen by shortest Hamming distances. In the case of multiple nodes with the same distance, a random node is chosen. This algorithm generates a path (shoot schedule) following minimal changes to casting in sequences of shots. It is exhaustive with all scenes scheduled, i.e. all nodes are included in the shoot schedule.
Clustering and hardcoded algorithm solution
We noticed in dry runs while minimizing for budget using exhaustive search that shots with same actors were usually scheduled together, an approach also taken in the greedy pathfinding solution. This is because clustering scenes with the same actors together decreases their working days, decreasing totalExpense. As clustering in a polynomial time operation, using it before running the search algorithm is optimal, decreasing overall search space.
2 stages of clustering are used:
1. Location clustering: Shots of one location are all grouped together. Each location is an array containing all actors needed at that location in all scenes. A path is generated between locations using Hamming distance between locations.
2. Scene clustering: Within each location, scenes with 0 Hamming distance, i.e. with the same actors, are grouped together. A set of all scenes per location is used to generate a shoot schedule using greedy pathfinding. Each node (scene) in this set has a unique set of actors.
Post-clustering, a hardcoded method is used. Scenes with the most expensive actors are clustered together first, minimizing the number of days they are hired for.
Clustering and A* search solution
Clustering still did not provide an optimal shoot schedule, because it only adds an optimization step to the greedy pathfinding solution. We use A* search [5] on the set of scenes post-clustering, i.e. each node has a unique set of actors
function Heuristic (h) = currentExpense(shootSchedule) / percentShotsDone : This heuristic is minimized in A* search. This heuristic is an approximation of totalExpense before an optimal shoot schedule is reached. This heuristic guides A* search to choose nodes (scenes) that add minimum expenses and maximum increase to percentShotsDone.
function Path travelled (g) = currentExpense(shootSchedule): Current expense of film, i.e. if film was to only shoot the already scheduled shots. Keeps track of cost per shoot schedule while generating the shoot schedule.
Greedy breadth-first search (BFS) and depth-first search (DFS) solutions
Greedy breadth-first [6] and depth-first searches [7] were also implemented with simply the above heuristic (h) without path travelled (g). These provided suboptimal results as they could not keep track of history of already scheduled shots.
Adding additional constraints
Constraints on location such as availability can be adjusted for by fixing certain shoots on certain days, i.e giving them a particular sequence number. These are the initial conditions around which the clustering step is done, and further A* search generates a shoot schedule with fixed sequence numbers. Sequence numbers are simply a function of the calendar, not the shoot schedule, hence they can be predetermined.
Simple constraint satisfaction solution
Simple constraint satisfaction was inefficient because many shoot schedules can be generated fulfilling all constraints. This is because actors are generally hired for long durations and can fill many generated schedules. High actor availabilities were too loose constraints to generate optimal schedules. This method also did not optimize for lower budget, and was little better than random gueses
Simple constraint satisfaction only takes into account actor and location availability with lots of possible solutions. Many possible solutions result in mostly random selection. This appraoch is inefficient when optimizing for budget. An optimal shoot schedule was not generated but this simple solution works and produces shoot schedules fast.
Greedy pathfinding solution
This solution greedily chooses scenes based on minimum Hamming distance. Greedy pathfinding does not give an optimal shoot schedule, being greedy in nature, but it does lead to insights like clustering and heuristics which are used to further refine solutions. Another problem with this algorithm is the random selection of shots with same actors (0 Hamming distance). Lastly, locations are not taken into account in this approach.
Clustering and hardcoded algorithm solution
Clusters simplify the initial set of scenes into unique scenes with unique sets of actors, important to eliminate redundancy. Minimizing expensive actor costs works well in films with skewed actor costs, particularly in films where the most expensive actor is significantly more expensive than others (100x), such as big-name celebrities. This approach does not produce optimal shoot schedules in other films where actor costs are relatively more uniform. While not optimal, this hardcoded method generates shoot schedules that are cheaper than the average budget across all possible shoot schedules and has useful insight for specific edge cases obtained from exhaustive search.
BFS and DFS solution
The heuristic generalizes search for all cases including edge cases but the heuristic alone does not provide algorithm with any information about the effectiveness of shoot schedules generated at every point. This results in choosing schedules that are not optimal
Clustering and A* search solution
A combination of heuristic and history (path travelled) paint an accurate picture of how efficient the current shoot schedule is for the search algorithm. The heuristic is mostly admissible as it almost always underestimates cost by assuming linearity in estimating total expense, but due to the addition of extra actors (since all members of the set are different), the cost increases more than linearly.
With these 2 functions, clustering and A* search solution is roughly optimal. The comparison between nodes (scenes) occurs by comparing a rough estimate of the total shoot expense, while current expense maintains a record of how efficient the current path is, which was not possible in depth-first and breadth-first approaches. This algorithm is used exhaustively with the stop condition being an empty initial set, i.e. all scenes have been scheduled. A unique number is given to each node, which is the sequence number. This is used to order the shoot in calendar dates, taking into account holidays and other nuances.
Clustering and A* search solution leads to roughly optimal shoot schedules.
A* search generates roughly optimal solutions (shoot schedules). It is only a good approximation because of the inadmissibility of heuristic function in certain edge cases. A new approach using opportunity cost is underlined and may lead to a more efficient algorithm.
The given problem attempts to tackle combinatorial explosion using a variety of optimization and pathfinding methods. A limitation of these methods that we have come across is that the assumption of an admissible heuristic. Towards end nodes, when all actors have been accounted for and no new actors come into scenes, the heuristic overestimates the total expense. Furthermore, this problem is very similar to travelling salesman [8] and requires a new approach.
Opportunity cost is the cost of choosing a particular node to traverse to. This is interpreted in fully connected graphs as a way to encode the information that any node can be travelled to from any node. This cost of choosing a node keeps an account all other nodes that were left out, as well as the fact that every node ultimately has to be traversed because this is exhaustive search. This is the next step for this research. We believe it will also hold insight into the travelling salesman problem.
We'd like to use this algorithm with an OCR program like Vision API [9] to directly read scripts, generate a list of shots and actors, and finally output an optimal shoot schedule on a calendar. This automates the entire process with the filmmaker only needing to work on their script.
[1]: Combinatorial explosion problem in AI. Wikipedia article. Link
[2]: Hamming distance. Wikipedia article. Link
[3]: Constraint satisfaction problem. Wikipedia article. Link
[4]: Patel A. Introduction to A*. Amit's Thoughts on Pathfinding. 2026. Link
[5]: A* search. Wikipedia article. Link
[6]: Greedy breadth-first search. Wikipedia article. Link
[7]: Mussmann S, See A. Greedy depth-first search presentation. Stanford University. Link
[8]: Travelling salesman problem. Wikipedia article. Link
[9]: Google Vision API. Google Cloud website. Link