I'm impressed by how much you have going there - it's a good example of how complex AI can get.

I've boiled the problem I'm facing down to this, which I want to present in more general terms:

The problem comes up when a task is split into smaller tasks which can be used in many contexts.

For example.

The precondition for 'Driving to a destination' is only that your car has gas and isn't broken down.

The precondition for 'Working at a factory' is that the factory isn't closed for the day.

If these two tasks are combined to make a task called WorkAtDayJob with the first task being to drive to the factory, and the second to work at the factory, then, the agent risks driving all the way to a closed factory unless he is able to evaluate preconditions that do not belong to the current subtask of 'Drive to destination', namely, that the factory isn't closed.

So there is a need for the subtasks to somehow inherit preconditions from the composite task (assuming that we placed the precondition of 'factory isn't closed' in the composite task WorkAtDayJob as well).

But on the other hand, if the car ran out of gas while going to work, it would be sensible to execute a subtask of 'Refuel car', and not cancel it even if the factory closed while at the filling station.

So, the preconditions must sometimes be inherited and tested each cycle, and sometimes not, depending on circumstances.

I now need to design a system that can do this...

Now we come to one of the main reasons AI can use so much CPU resource (and to some extent more memmory) -- the amount of preevaluation and reevaluation you have to do constantly.

When you have a bunch of potential solutions to a given goal you have to evaluate ALL of them in order to pick ones that are valid and then somehow have a metric to decide which one would be 'best'. You can use some culling techniques to quickly discard some, but then the methods to 'judge' which has the most chance of success (or potential possibility of succes when information is lacking).

Every time your situation changes sufficiently you then have to do reevaluations of those NOT picked solutions to see if they would now be a better pick.


WorkAtDayJob() decomposes naturally into

GetTo(Factory)
Work
GetTo(Home)
SleepAtHome()

When preplanning you would seek solutions recursively, so the
GetTo(Work) would look for a solution like

DriveOwnedVehicleTo(X)
or
TakePublicTransitTo(X)
or even
WalkTo(X)

and when they are evaluated to see which is best a multidimentional 'cost'
would be calculated as to how much 'money' would be consumes and how much 'time' is consumed and possible what the 'risk' might be.
You woudld have to figure out what each is worth to add up one number to compare. You may have to use functions that adjust the value (ie - the cost of time escalates as you waste more and more...)

If you have a car DriveOwnedVehicleTo(X) is valid (and if the Bus doesnt go near the factory TakePublicTransitTo(X) might not be or would generate a high (poor) 'cost'. WalkTo(X) probably will always work but costs proportionally alot more in 'time'.

Supposing DriveOwnedVehicleTo(X) is valid then it would have run pretests for
operational state already but now the gas factor would be looked at (as it doesnt block, but may have to have a ProvisionFuelforVehicle(X) subgoal which may require a gas station stop. This would be evaluated and would add more accumulated time for this solution. Contigencies like flat tires cannot easily be predicted (but would have solutions if they happened). A general
delay 'cost' might be added into the cost evaluation based on the probability ofthese complications (nmore complex solutions might accumulate so many as to lower their likelyhood of being chosen). The factor might be based on statistical (historic) measurements of previous execution of the same solutions use.



The overall task WorkAtDayJob() has to fit into 24 hours as a precondition (and with Sleep() and Work() each having some minimum that would give you a disqualifying maximum transit time sum. Similar sums would exist for 'money' costs and max allowed risk .





The solutions available for an object to fulfill a given task can be inherited from a class (not nessessarily a class as in C++, but one where the 'class' bestows access to a set of code solutions which will carry out the tasks needed to reach the goal). The Solution Space is searched and the resulting matches are the evaluated with specifics of the situation. These solutions might vary ing 'specifiness' such as :

Get() -- very general methods of aquiring things

Get_Typex() -- more specific at getting a particular type of object

Get_Typex_at_LocX() which is even more specicif and may actually tap into a object own set of mappings gathered previously (like the last few times it ran
Get_Typex()

Usually the more specific solutions have a better chance of succeeding and having one available may allow not having to evaluate less specific solutions.



A 'drive powered wheeled vehicle' class would have the driving behaviors considered in its logic (including some for handling 'fuel' contingencies -- set of which are probably additional classes).
Pathfinding for this type of movement would take roads into consideration much more than other movement types.


Something Ive examined previously is the effect of an objects 'preferences' which control evaluations of costs. Example is the Get(X) which is very generics and might have possible solutions like:


Steal(X)
Buy(X)
UseItemIHAve(X)
Borrow(X)
Make(X)

the Steal option would make a check against the Person Objects preference for
doing things Lawfully (high value adds high cost (a multiplier) to unlawful acts) and maybe also cost of additional 'risk' with a preference factor for not taking chances (Risk Aversion) would likewise have higher cost multiplier in effect. (You can get very complex with these preferences such as a 'greed' factor adjusts the acceptability of a propesed compound-solution task -- if the summed money cost is positive enough it might overrride a high risk value)



Notice each solution is itself fairly complex and may decompose into more than a few levels of sub goals/tasks.


Reason #2 for greater CPU usage of AI -- combinatoric explosion of possibilities in a more complex detailed simulation. Reactive in (near) realtime multiplies it even further. Memorywise, maintaining
historic data for previous actions can get voluminous (and such a processing problem in itself that it might have to be rebuilt offline)


--------------


Another fursther thing for more complicated simulations of behaviors : evaluating 'certainty' for different solutions.

Missing information increases uncertainty. Even with information available, evaluating it in complex situations and generating probabilities can be quite hard. Minor factors can have major impact. A whole area of AI deals with
factoring situational data.

Even after you have some way to generate probabilities, it increases the evaluation logic. (Remember I mentioned more versatile solutions can be better than solutions based on required circumstances). Certainty becomes another factor to add into the 'best' pick evaluation.

A high payoff task migh compensate for a low expected success probability (adjusted by the uncertainty). A preference of 'optomism' adjusts uncertainty in the direction of success ( versus in the expectation of failure)

Your precondition system would probably be based on a object 'token' which is added to a list maintained by each task.

The tokens have to be added to a task and removed as the task advances thru its steps and is evaluated at appropriate spots (as in before the 'action' phase of my FSM where it can be rerun for cyclic actions (retries/repeats).


Inheriting parents sets could be done by maitaining a stack of tasks/subtasks and checking upwards the levels precondition list.

It may turn out that there are few dependencies being passed (cost limits (time/resources/risk) is the one I mostly expect) and most other preconditions are local to each subtask. With that each subtask is allocated a portion of the 'cost' limit so a new token with the small value is built on initiating the subtask. The inherited preconditions could be added via well defined parameters (which might accept generic preconditions for versatility).

It sounds like a good idea to have the composite goal grant time resources to each subgoal, and then test the elapsed time in the subgoal as part of the other precondition tests.

Maybe preconditions could be designed as predicate (boolean) functions, encapsulated in a C# delegate. When a subgoal is added, it is the parent that decides which of its list of predicates should be given to the new subgoal as preconditions. On each tick, the subgoal will call all the precondition predicates in its list.

Im still working on the design of my precondition mechanism.

I would have a local list for the immediate task being run (in focus) which could include preconditions passed in from the parent (like the time limit).
Being local it then can be easily manipulated (FSM adding/removing) and cleaned up. Its then also seperated from all higher ones sothat it can be reevaluated at a high frequency.

But then there also would need to be the preconditions that come from upwards on the task hierarchy which are external to the current task. That list of preconditions would likely be run on a less frequent interval. If they fail they invalidate the task chain upwards (in mine I include the task id which created it and the contingency required to react to it (my FSMs have steps which can be referenced -- so the task step also could be included).

Different condition type would be handled differently -- time limits are cutup and remade for each task level , so they wouldnt be put on the extenal
precondition list. They would be handed down as a seperate parameter and become a local condition (to be inturn cutup and passed down to subtasks).
Encompassing requirements for a whole task tree (like key items being in inventory) would be on the external list that would be passed down recursively to all subtasks.
Ex- if task is to go hand in the rent and you lose the money at any point (up to the time it is delivered) the whole task is invalidated -- notice thought that condition should be disabled at a midpoint where the money is delivered (when the final steps of the task is the return movement where the possession of the money is now irrelevant)

So a mechanism to diable (or remove?) external preconditions is also needed.




The conditions themselves are coded as either:

a standard (precoded) test ordinal (ie 23 = timelimit test) and some coefficients (data) for the test (ie- the cutoff time value). I usually lean towards fixed structs (I like free pools) with expansion blocks (dynamic large sized) only for exceptional cases.

Token = func ordinal + fixed (variant) data block + contingency reference (task + step)

OR

a function call to a custom test (which could be constructed (use an interpreted script language) or be a (compiled) code block in handler blocks imbedded using the task script wizard Im working on. Coefficients for func parameters would be included in the token...

Token = function pointer+ fixed (variant) data block + contingency reference (task + step)




My FSM mechanism allows explicit testing of tokens at custom points in the FSM script for flexibility (those condition tokens then could be just local data to the FSM along with any local state variables used).
The local precondition list mechanism would also be there and the external list of conditions seperately (passed down). Depending on the logic flow there could be different optional places to test the local/external preconditions and the wizard would make sure it got done by default but allow customization.




-----------


The task evaluation functions Ive mentioned before for estimating resource usage/viability of a solution instance is another area Im still considering designs.
I was going to have a seperate 'evaluate' function created for each task FSM script -- hopefully done via the task script wizard, but with sufficient ways to customize the logic. Reuse of custom evaluation functions (creation and adding to the options pulldown lists) and parameterizing (with good defaults).
When the script is built up via the wizard and subtasks are inserted into the FSM sequence then they would add in their own effects on the evaluation (likely you would recursively get their evaluated/estimated cost/success/risk result and sum them up for their parent). The full 'estimate' function
would be built as a last 'compile' step after editing(via wizard) the task script. Th wizard then creates C++ code so that the FSM can be fully compiled for running efficiency.


Unfortunately where alot of unknowns inhibit detailed preplanning (those 'late'
solvers being called to resolve planning 'on-the-fly') and then only generalized estimations can be used with what data IS available/can be foreseen.
(as I said, Uncertainty greatly complicates the AI ....)
Consider that you might not know what 'facts' will be available when the pre-planning is done (on goal activation??) so the planner has to decide which bits it can plan in detail and which will have to be added as 'late' reolution.

When talking about the difficulty, combinatorial explosion, etc. in AI, do remember that very often, the goal of AI (as in, the goal of the AI developer) is not to have the AI do things perfectly, but to have the AI appear human. Humans very rarely consider all possible solutions to a problem and do a detailed comparison. More commonly, humans simply go with an approximately good solution or even just one that is known to work.

Of course it is nevertheless interesting to try to solve these hard optimization problems.

Quote: Original post by Prefect
When talking about the difficulty, combinatorial explosion, etc. in AI, do remember that very often, the goal of AI (as in, the goal of the AI developer) is not to have the AI do things perfectly, but to have the AI appear human. Humans very rarely consider all possible solutions to a problem and do a detailed comparison. More commonly, humans simply go with an approximately good solution or even just one that is known to work.

Yep. Chapter 6 in my book is entirely on that phenomenon. We humans are startlingly non-rational.

Getting the 'intelligent' objects in the game to appear to behave semi-intelligent when not using staged/hand choreographed sequences will be challenging enough. Mediocre actions and results are sufficient in a complex world which has alot of unknowns (and the object are forced to make due with a lack of information).

The combinatoric explosion is still there even if you dumb down your behaviors as even if the same strategy is used over and over, the details of the execution of it still have to run (and you had to FIND/MATCH that strategy to the game situation). Doing 'charge at player and start swinging and little else' all the time is what we mostly have today. Just having them doing things in a varying environment and react instead of standing like mennekins or walking the same waypointpath without deviation would be a major improvement.



Considering 'perfect', estimation functions can really only be generaizations which will not catch specific circumstances and the solution matching will always be a generalized pattern also lacking endcase stituations.
The logic has to be precanned and will always have holes in it.
Predicing actions of the player(s) adds a magnitude or more complexity ontop.


Sensor information can be manipulated to limit an objects perceptions. Quality of information greatly effects Certainty and a comprehensive AI would have to have understandings about the quality of the information it received and made use of (and adapt to).

For 'non-rational' consider social roles (object having more than one) where there are conflicting roles in specific situations, where the choices made can be quite convoluted. Ive looked at objects having 'preferences' which shape the way they select their goals and evaluate/execute their solutions.

[Edited by - wodinoneeye on January 11, 2009 10:02:13 PM]