At the core of any project is a problem to be solved. I am not talking about the technical setup/integration/debugging type problems, but the core value that the project is delivering. In our drone control program the core value is efficiently routing and controlling drones.
Assigning multiple drones to tasks is a version of the multiple travelling salesman problem with constraints. The brute force approach is order n factorial, which is not feasible on current computers for more than 20 cities (depending on the problem definition). This is a very interesting problem especially to the logistics industry, but is also relevant to other industries like advertising, where matching advertisements to web users with good predicts click-through rates is crucial to their profits.
The most obvious solution is to order the tasks in priority order and assign the closes drone down the list.
We can improve our greedy solution by applying some optimization techniques. Firstly we can benefit from the Munkres (Hungarian Method) solution to the Assignment Problem which quickly finds the best matching assignments. We can use this method iteratively to produce a schedule.
(defn weight [a t]
(distance (get-in t [:from :location])
(a :location)))
(defn assign [world [drone mission]]
(update-in world [:drones (drone :id) :missions]
(fnil conj #{}) mission))
(defn plan [world]
(let [agents (world :drones)
tasks (seq (world :missions))
solution (solve agents tasks
(weight-matrix agents tasks distance))]
(reduce assign world (solution :assignments))))
Munkres provides the optimal assignment for 1 task each, but we are looking at many tasks. The iterative approach gets around that limitation but at the sacrifice of optimality. There may be better schedules that we are missing.
These set of algorithms use a heuristic to quickly construct a schedule, then fix it up as best possible to make it even better. Our original heuristic was nearest neighbour. Another heuristic is to identify chains of jobs that should be done by one drone.
To try these approaches first we construct an implicit graph of the connections that the drone range of 10km allows. This will allow us to explore other possibilities other than closest in range hopping.
by priority -> nearest match current + future
mission “X from A to B” + priority/time
Compare greedy vs iterative Munkres vs chaining, vs construct/modify.
There has been error in communication with Booktype server. Not sure right now where is the problem.
You should refresh this page.