Return to “Suggestions”

Post

AI Task Delegation

#1
After reading Josh's comments in his devlog for Dec. 28, 2013, about the delegation of goals to factional subordinate NPCs, I was surprised to see that there's no thread specifically about delegation and how it might work.

Fixed. :)
JoshParnell wrote:[T]he "efficiency" of task performance is influenced by certain state variables, but how do we encode that knowledge? .... To really allocate resources efficiently, one must have an understanding of this "efficiency," such that resources can be fitted to their most appropriate task.
...
There's an interesting question that I ran into today concerning delegation, which I call 'faith.' That is, how much do you trust that someone else can get something done?
The general question is how to decide which NPC to offload a task to. Just as something to knock around (bearing in mind that Josh already has his own ideas), here's a quick concept:

D = E + (A * U) + (R * C)

where:

D = delegation
E = efficiency
A = availability
U = urgency
R = reliability ("faith")
C = criticality

Efficiency is pretty much as Josh described it: a numeric assessment of how well an NPC's resources match up with the task requirements. (This gets its own calculation.)

Availability is a negative number that reflects the cost to get the NPC started on the proposed task, such as distance if there's a physical item or location involved that the NPC needs to travel to reach. This would be multiplied by the Urgency of the task -- the more urgent the task, the more the NPC's Availability matters. (Availability should be something like -9999999 for an NPC flagged as already fully dedicated to some other task.)

The NPC's Reliability (how well they've performed on similar tasks in the past) is a number from -10 to +10 (or something similarly ranging from negative to positive) that is multiplied by how important the task is. You wouldn't give a Critical job to someone you didn't know, or to someone who hadn't successfully completed that kind of task for the delegating NPC in the past.

Whichever NPC gets the numerically highest score gets the task. A task that has time value but isn't strategically important (i.e., Urgent but not Critical) would go to the closest NPC with the necessary resources, while a task that's very important but doesn't need to be completed immediately can go to the most reliable NPC regardless of his current location. And a task that's both Urgent and Critical would go to the nearest and most trusted subordinate.

There are plenty of practical questions that could affect this calculation. One is whether communication takes time over distance. If tasks can be assigned instantly to any subordinate regardless of location, delegation is a lot more efficient than if orders have to physically travel through space. In the latter case, an NPC's Availability is much more important.

Another question is how to break down goals into tasks that are appropriate for the next lower level of subordinates. You don't want to expect subordinate NPCs to do things that are your responsibility. But you also don't want to give an easy task to an experienced NPC, or a job that requires great tactical skill to an NPC who's an excellent strategist (or vice versa).

A distinction probably also needs to be made between jobs that are "atomic" and compound goals that can broken down into simpler compound goals or atomic tasks. Atomic tasks, such as "attack that ship" or "carry this general freight to Location X," are best delegated to rank-and-file subordinate NPCs. But goals that can be broken down into tasks need to be delegated to NPCs who are in the middle to higher levels of a factional hierarchy, who then break them down into new lower-complexity compound goals or (if they're the initial level of leadership) into atomic tasks.

This just sort of scratches the surface of how delegation could be implemented. Other thoughts?
Post

Re: AI Task Delegation

#2
Excellent and insightful thoughts on delegation, thanks Flat :thumbup: I had not considered using so many nuanced factors. Realistically, I'm not sure how many of these the AI will be able to evaluate accurately, but R and C at the very least seem feasible. A and U will probably be trickier.

A is conceptually straightforward, the issue is that it requires a plan from the perspective of the delegate in order to really know the distance. That's just a computational problem, as, ideally, we don't want to have to formulate a whole plan just to determine which person to delegate to. Again, just a matter of efficiency, but not a conceptual problem.

U is not so conceptually straightforward to me - what does it mean to be urgent? I suppose that it means the opportunity that the plan hopes to exploit will only exist for some window of time. But that seems to require a very strong understanding of temporal reasoning. Unfortunately the current AI only has a simplistic understanding of time, it is not does use full-blown temporal logic. I am open to suggestions or alternate (preferably simply) ideas of what urgency might mean :)

IMO communication over a distance should probably be instant to mitigate complexity. Open to discussion on that (although it's probably a separate topic).

I think the delegation hierarchy kind of solves itself simply by the nature of hierarchies. If you have 3 subordinates, each of whom have their own subordinates, you simply assign 3 goal nodes to them. They will construct plans to solve those nodes, and, where applicable, employ their own subordinates in turn to solve resultant parallel nodes. This process will unfold recursively as the planning tree and availability of subordinates allows.
“Whether you think you can, or you think you can't--you're right.” ~ Henry Ford
Post

Re: AI Task Delegation

#3
JoshParnell wrote:Unfortunately the current AI only has a simplistic understanding of time, it is not does use full-blown temporal logic. I am open to suggestions or alternate (preferably simply) ideas of what urgency might mean :)
I'm not fully up-to-date with how your AI works, but how about defining urgency as the negative of the time-derivative of the expected utility from a given plan? That is, if at time t your AI calculates the expected utility of a plan to have value U and at time t+1 it calculates the expected utility of the plan to be U', then the urgency would be equal to -(U' - U) = U-U'. Using completely arbitrary units, if U is something like 10, and U' is 5, then the urgency would be calculated at 5.

This might work decently in some situations and would probably completely suck in most others. An example where it might work well is this: say an NPC wants to mine out an asteroid field, and the field presently contains 100,000 utility points worth of ore. But if the field is already populated by miners, then the next time this plan is re-assessed, the field contains only 80,000 utility points worth of ore. The faster the ore is disappearing, the greater the negative of the time-derivative of the expected value of the plan to mine out the field is, and the more urgently the NPC will feel the need to initiate the plan before the other miners get all of the ore.

This approach would only really work if the expected utility of a plan fell off constantly over time rather than remaining constant until it suddenly plummeted to zero (as would be the case of a plan that would work just as well so long as it was enacted within its window of opportunity). For that, you'd need your AI to understand the concept of time and be able to make predictions about the future utility values of plans, and you said your AI can't do that yet.

Best I could come up with in the minute I had after reading this, sorry if it's not very helpful.
Post

Re: AI Task Delegation

#4
Urgency could be a fixed number, does not have to be calculated. For example, a space station that is lacking resources could put more urgency on trading/mining tasks. While a station that is damaged could put more urgency on repair tasks. A station under attack could put more urgency on getting defense ships, or putting up contracts for mercenaries. So Urgency could be a fixed number, and does not necessarily have to be calculated every time... It would help though, I would love to see a station under attack put more resources on defense, and not keep mining like nothing happened (as seen on some older games).

Online Now

Users browsing this forum: No registered users and 1 guest

cron