A game I'm currently working on will need the ability to efficiently assign large numbers of workers to large numbers of jobs. A worker must travel (on a 2D plane) to the site of the job before performing the job. The goal, then, is to produce assignments for workers which minimize overall travel time in order to maximize efficiency. Now, of course, in the general case this is quite a hard problem. (Example: 1 worker and many jobs turns the problem into Travelling Salesman.) However, I'm perfectly happy with an empirically well-performing algorithm; contrived worst-case scenarios are unimportant to me, especially since I can game-design around them. The big assumption I'm willing to make is that a greedy search can work well enough. Here's my current thinking: Build a kD-tree of all jobs. Now, until all jobs are gone or all agents are gone, perform nearest-neighbor queries outwards from each unassigned agent to the nearest job. The closest job-agent pair is added to the assignment list, the job is removed from the kD-tree, and the agent is removed from the unassigned agent list. Repeat until you run out of jobs or agents. There's problems with this, though. Assuming a agents and k jobs, the runtime performance is O(a2 log k), not counting the time to build and remove nodes from the tree (I'm unsure of the complexity of these operations). This stems from not being able to use any but the lowest NN-distance, since any other agents might have found the same job as the closest neighbor. Alright, so new modification. Each unassigned agent has some distance to the nearest job. The agents are placed in a priority queue, ordered by distance. The lowest-distance agent is popped off and examined. If its closest job is unassigned, then the assignment is made. Otherwise, the agent performs a new NN query (with jobs assigned since its last NN query no longer in the tree). The performance of this algorithm, then, would be O(m log k), where m is the number of "misses" (NN-recomputations due to already-assigned jobs). It's been awhile since I studied algorithmic analysis, and I have absolutely no idea how to estimate m. I have a sneaking suspicion that m might be O(a2), which would make the algorithm equivalent to the earlier one. Thoughts?

I don't see how a kD tree would help here? Are you aligning everything on an axis (whats wrong with a BSP tree)? Also, if you assign workers at the start of the program, why not spawn workers close to thier job?

For the algorithm, O(a^2 log k) is the time it takes for every agent to find a job if you just loop thru each of them. You're priority stack tries to assign jobs to nearby workers, and take them out of a quickly right? In that case, your big O would not change (you could arrange the stack such that it alway picks the last one).

Quote:Original post by sevensevens
I don't see how a kD tree would help here? Are you aligning everything on an axis (whats wrong with a BSP tree)?

The kD tree is used for efficient NN search. AFAIK, generalized BSP trees are rarely used for NN search because of the additional mathematical complexity.

Quote:Also, if you assign workers at the start of the program, why not spawn workers close to thier job?

I don't. This is used for periodic full reassignments.

Quote:For the algorithm, O(a^2 log k) is the time it takes for every agent to find a job if you just loop thru each of them. You're priority stack tries to assign jobs to nearby workers, and take them out of a quickly right? In that case, your big O would not change (you could arrange the stack such that it alway picks the last one).

I'm not sure what you're saying here. As I said, I'm interested in average case complexity, not worst case complexity.

In general, would the number of workers (a) be smaller or larger than the number of jobs (k)? Is there a reason why the naive approach of just iterating through each job and assigning the closest worker would be undesirable (that should be O(ak))? Have I misunderstood the problem?

Quote:Original post by wodinoneeye
What is the ratio of movement time (ave distance) to the time to carry out the job. (Ive seen games where the walk time was significant and thus increased the importance of smart assignments (best fit)). If the travel is insignificant
then a crude (cheap) assignment method would be less noticible/important.

That's a good point, and in a lot of cases workers will spend more time on jobs than walking between jobs. However, they need to look intelligent, so even if they're only walking the wrong way for a little while it's a problem.

Quote:Will there be blockage/traffic jams that may increase the travel time (so simple distance may not be an adaquate metric (similar goes with mazelike environments).
Might some workers have no valid path to particular jobs?

The area will be a little crowded but only minimally occluded by scenery. Based on tests I've done, I feel comfortable assuming that travel time will be roughly proportional to euclidean distance.

Quote:Do 'workers' have a home they work out of (so the return time at the end of a 'workday' is also part of the efficiency....

Some do, but they are not handled by this algorithm.

Quote:Can the assignment be staggered (timewise) and processed in subgroups -- to decrease the 'squared' effect of the sort/prioritization ?? (

I'm already doing this with groups of workers who are able to perform different job types, but I don't know how to partition them further in a way which wouldn't undercut the algorithm.

Quote:Original post by Trapper Zoid
In general, would the number of workers (a) be smaller or larger than the number of jobs (k)? Is there a reason why the naive approach of just iterating through each job and assigning the closest worker would be undesirable (that should be O(ak))? Have I misunderstood the problem?

That approach can lead to artificial starvation of jobs which are far down in the list. Still, I should do some tests to see how much of a problem this really is.

Quote:Original post by Sneftel

Quote:Original post by Trapper Zoid
In general, would the number of workers (a) be smaller or larger than the number of jobs (k)? Is there a reason why the naive approach of just iterating through each job and assigning the closest worker would be undesirable (that should be O(ak))? Have I misunderstood the problem?

That approach can lead to artificial starvation of jobs which are far down in the list. Still, I should do some tests to see how much of a problem this really is.

I've been thinking about the problem a bit more. If this is similar to one those strategy management games, then I'm taking that this worker to job allocation scheme is running relatively frequently. If so, then it should be rare that you are put in the situation that there is an overabundance of idle workers and jobs. Either there will be more idle workers than jobs (who will then quickly take any jobs as soon as they are available), or there will be a backlog of jobs that workers will move to once they have finished there tasks.

If that's the case then you might want to have different algorithms for both the case of many idle workers and many available jobs; maybe updating a structure of job priorities as new free jobs become available, or spreading the pool of available workers over the domain area so they will be more likely to be close to any newly available job.

That's a really good point. I'm coming to agree with you that different algorithms need to be selected at different times. In particular, different "levels" of my game will have wildly different job/worker ratios.

One thing that worries me, though, is the transition between the two systems. When the algorithm switches over, half the crew simultaneously pivots and starts walking towards a different job than they were walking to before. How to deal with the unnaturalness of this effect?