Assigning worker tasks [closed]

Question

In a simulation, workers must move around a map performing tasks.

Each simulation 'tick', they can move one square.

Performing the task once they are adjacent to it takes 10 ticks.

Task squares cannot be passed through. Squares with workers on cannot be passed through. More than one worker can work on a square.

Workers are not competing with each other; the objective is to complete all the tasks as quickly as possible.

Added: ideally the algorithm should be straightforward to conceptualise and simple to implement. Isn't that what everybody wants? Its a big plus if its efficient e.g. the model can be updated and reused, rather than recalculated from scratch often. Ideally it'll be able to use local optima so its not trying to brute-force an NP problem, but avoid being overtly greedy and think ahead a bit, rather than essentially random wanderings where workers pay little heed of the plans of others.

Here is an example:

Workers 1 and 2 must complete the tasks on squares A,B,C and D.

How do you decide which worker does which task?

It seems self-evident that 1 should do A and 2 should do C.

1 is 4 squares away from A, so will have finished doing it in 14 ticks. Where should 1 go next, and why?

And what if there was another task - E - is placed directly above B?

What is the logic that a worker uses to decide where to proceed next?

What I've tried:

This being a hobby RTS game, I've tried making it so idle workers proceed to the nearest task, or proceed to the nearest task which no other workers are doing.

This greedy approach has proved to be glaringly inefficient and player testing makes it clear its untenable. Because the strategic mining/building/farming is key to the game, and because I don't want the player to micro-manage and route all workers, I'm looking for a fairly fair and reasonably optimal algorithm that workers can use instead.

Answer 1

Even with one worker this is an NP-complete optimization problem (it then becomes the traveling salesman problem) so let's forget about "optimal".

If you know that worker 1 will handle tasks A1, A2, ..., worker 2 will handle tasks B1, B2, ... and so on, then you can, after that decision is made, try to solve the independent traveling salesman problems one by one, and you get the schedules and paths for all your workers.

However, the problem is that you can't know how long it takes to complete a set of tasks A1, A2, ... for a worker before you have solved the traveling salesman problem for that set because walking time impacts the total time to carry out the tasks.

Because it's just a game, and the workers can be assumed to be not optimal thinkers, I would use a stochastic process:

1. Assign all tasks to all workers randomly
2. Use a greedy algorithm to calculate an upper bound on the walking time for every worker within the worker's task group
3. Try a random move, either move one task from one worker to another, or swap tasks between two workers
4. Accept that move based on tabu search or simulated annealing principles, depending on whether the move decreases the upper bound on maximum execution time (walking time + task execution time), so that the goal is to get the last task to finish as early as possible
5. After N iterations, stop, and calculate better solutions to the traveling salesman subproblems e.g. using stochastic search, or explicitly if the problems are small (e.g. less than 10 tasks per worker)

Answer 2

Instead of greedily assigning workers to the nearest task, try greedily assigning the most distant task to its "nearest" worker - that is, the worker whose path passes closely and has enough slack time to handle it. This way you have a (greedy) notion of the smallest time it takes to complete all the tasks.

For example:

D is the 'most distant task', even without defining that term yet, so assign D to 1. It is 15+10 units away, so set t = 25 and the slack on 2 to 25.

Now here is the distance cost of assigning the next task, taking into account shortest routes.

    A   B   C   D  
1  10  22  24   -
2  29  19  18   -

But here is the true cost according to the greedy idea; the increase to the maximum time t.

    A   B   C   D  
1  10  22  24   -
2   4  0    0   -

Since C has the highest cost (it's the most dangerous task from a greedy perspective), assign C to 2.

The next costs are as follows

    A   B   slack    A  B
1  10  22     0     10 22
2  21  11  (-)7     14  4

Assign B because 22 is the largest increase to the max time t. Assign it to worker 2.

...

There are many approaches to a knapsack problem but if simplicity is desired this is probably the next thing to try. Maybe store the shortest paths between tasks. It's an overtly greedy way that does think ahead a bit!

Answer 3

This indeed sounds a lot like the (already mentioned) Travelling Salesman Problem (TSP, http://en.wikipedia.org/wiki/Travelling_salesman_problem) for multiple agents. Which is actually a problem similar to Multiple knapsack (MKP, http://en.wikipedia.org/wiki/Knapsack_problem#Multiple_knapsack_problem) or even Bin packing (http://en.wikipedia.org/wiki/Bin_packing_problem).

There is a group of algorithms which might be suitable in this situation, and it is called 'Ant colony optimization' (ACO, http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms).

To combine the two, there are implementations that use ACO to solve MKP problems; this seems like a good way to go in this case, for example:

http://www.researchgate.net/publication/221246039_Probabilistic_Model_of_Ant_Colony_Optimization_for_Multiple_Knapsack_Problem