I'm in need of some input to realize a simple and robust logistics ai. My goal is pretty standard: order some goods => transport the order to a production facility => produce goods => deliver goods to the client The problem is, that you can't tell my agents what to do, they have to decide it themself. So, the client places some orders "somewhere", my agents need to transport them to an according production facility, some other agents produce goods for this order and eventually any other agent delivered the good to the client. Is there any existing algorithm which solves this or a similar problem ? Maybe I'm not seeingthe wood for the trees. So far I came up with the following solution: I got three objects: a request, a confirmation, a delivery Whenever a client wants to order something he creates a request and a confirmation, each one holds the client address. The client keeps the confirmation to get back later to look if his order has been delivered. My "transport" agents check locations for requests, take them and try to deliver this requests to production facilities. If none production facility is near it will try to take it to some storage site. Once a request reaches a production facility other agents will try to produce the requested objects (in this case new orders of needed resources will be created). Once a agent finished the production of a good it will exchange the request with a delivery object(client address will be copied) which holds the produced good. Now a "transport" agent, checking location for location, will take up this delivery and transport it to the client address. Eventually the client will check frequently the client address from his confirmation if the ordered good has been delivered. Hmm... not the simplest way to go, but I hope it is a robust way. I don't need a optimized way, but I'm not sure if it will work. Is there the chance of starvation, deadlocks, will the whole system collapse ? Any thoughts ? -- Ashaman [Edited by - Ashaman73 on August 6, 2009 3:58:03 AM]

Thanks Ashaman for this problem it seems interesting. I'd like to know what's Logistic AI

Thanks

Abdelrahman

I meant logistics (instead of logistic).

@Ashaman, thanks for reply

This sounds like something which needs several layers of solution. The main requirement is a blackboard system on which the "I need", "I have" type messages would appear.

So, your client says, "I want 100 axes". and it writes it on the blackboard.

"goal 6786: Deliver 100 axes to this location".

Your agents scour the job adverts looking for things they can do. They're allowed to partially fill orders. They'll tend to prefer doing completed requests (note that request 3 in that list isn't finished yet) and requests near where they are.

So, a carrier might look at the jobs and say, "Hey, I can carry axes. I could do #1. Where can I get axes from?" if there's a storeroom with axes, it's posted a message saying "I have 10 axes available", the carrier might say "OK, I can partially fill the order" and set off to get them. Meanwhile it takes down that advert and puts a new one up saying "Goal 6786: Needed, 90 axes (10 done already)".

A toolmaker who is idle wakes up, looks at the board and says "OK! I can make axes!" He takes down that notice and puts two up saying "Needed, 90 wood (to make axes job number 6786)" and "needed, 90 metal (to make axes job number 6786)".

Another courier wakes up, sees the notice saying "90 metal needed" and sees an advert from a mine saying "270 metal available". He books out 90 of the metal, takes down the needed notice and goes off to fill it.

Now the way you stop funny effects happening with chains poaching stuff off each other and deadlocking is to tag the goods. When the courier collects the metal, you tag it with a note saying "90 metal, destined for toolmaker number 7, to make axes, to complete goal number 6786"

If you tag them all the way along the chain, your raw inputs end up allocated for production which should stop deadlocking. Starvation can happen, but that's why Settlers is fun..

So all the processing along the way becomes simple; at each stage, the workers simply advertise their needs and leave them to be filled.

When the metal and the wood arrive at the toolmaker, he has all the information to do the work and then to advertise "90 Axes available; for goal 6786" and a courier will pick them.


Right, then cute stuff starts;

You can time delivery. If you time the delivery of end results, you can adjust the costs of military solutions. If your military planner decides it wants to attack something, it can be guided to building units which are cheaper in time to make; this means if the player comes and kills all your woodcutters, the military system will stop asking for spearmen, and just ask for swordsmen instead...

Time the delivery of raw materials, and as they increase your building planner can be told it needs to make new mines etc.

@Katie: Thanks for your input it helps alot.
Your solutions sounds similar to mine but more mature.

Quote:
This sounds like something which needs several layers of solution. The main requirement is a blackboard system on which the "I need", "I have" type messages would appear.

So, your client says, "I want 100 axes". and it writes it on the blackboard.

"goal 6786: Deliver 100 axes to this location".

The solution was that my request objects represents the messages, but a centralized blackboard system seems to make the message transportation obsolete which sounds better.

Quote:
Your agents scour the job adverts looking for things they can do. They're allowed to partially fill orders. They'll tend to prefer doing completed requests (note that request 3 in that list isn't finished yet) and requests near where they are.

So, a carrier might look at the jobs and say, "Hey, I can carry axes. I could do #1. Where can I get axes from?" if there's a storeroom with axes, it's posted a message saying "I have 10 axes available", the carrier might say "OK, I can partially fill the order" and set off to get them. Meanwhile it takes down that advert and puts a new one up saying "Goal 6786: Needed, 90 axes (10 done already)".

A toolmaker who is idle wakes up, looks at the board and says "OK! I can make axes!" He takes down that notice and puts two up saying "Needed, 90 wood (to make axes job number 6786)" and "needed, 90 metal (to make axes job number 6786)".

Another courier wakes up, sees the notice saying "90 metal needed" and sees an advert from a mine saying "270 metal available". He books out 90 of the metal, takes down the needed notice and goes off to fill it.

Ahh.. I like this one, it makes the single tasks quite simple.

Well, this sounds good, but it will need a 'virtual' blackboard', won't it ? Will it work with a 'real' blackboard, where each agent has to go to the blackboard to check for orders ?
Will it still work if I make several blackboards which each blackboard holding its own set of messages ?

--
Ashaman

"it makes the single tasks quite simple."

This is always the trick with AI; break it down until the tasks are simple.


"Well, this sounds good, but it will need a 'virtual' blackboard', won't it ? Will it work with a 'real' blackboard, where each agent has to go to the blackboard to check for orders ? Will it still work if I make several blackboards which each blackboard holding its own set of messages ?"


I don't see why not, provided the agents know where the blackboards are (in the game work). They can just visit nearby blackboards to see what work is available. Possibly have them centred on one board they think of as their main one. Maybe if they get starved of work, they could "migrate" to regarding another blackboard as their main one.

If this is medieval game, it would make sense to have the town hall hold the blackboard. This way you'd get all the workers popping in and out to get their assignments.

You could even have the blackboards have the locations of other boards -- and couriers who carry information between the boards. So if one board has a lot of work on it and the local workers are feeling overwhelmed, they could send a message to another board saying "Work available at XY, come and help!"

Messages on the boards that get too old could be passed on to handle town<->town commerce. {Of course if they get too old, you want to prod the player (or the main AI) that the order can't be completed so they can solve the problem.}

Once that overload was handled, the workers would start to migrate out again looking for more work. You'd get this brilliant effect of a migratory workforce showing up for the big projects and then dispersing and it all just falls out of simple rules.

It gives you all sorts of very neat gameplay possibilities; The other player is building a castle, but you don't want to attack it yet because you need more troops... you can slow down the construction while you get ready by sending off some soldiers to hunt down the couriers going to fetch workers from other towns...

Katie, thanks very much, this was the right hint :)

After reading more about blackboard ai I will try to implement a distributed blackboard system.

--
Ashaman