Dear People, A concept that I have pondered for a while is the development of an AI toolkit, one which has simple OO classes for NN''s, Genetic Algorithms and possibly pathfinding. A reply I made ot Fratt''s post regarding the engine that could stand AI was that it is difficult to create a generic pathfinding library, because we don''t know the syntax of the map file, and we don''t want to restrict the end-user of the toolkit by pre-setting the syntax. It is quite easy to create a NN that loads scripts to describe the behaviour etc (i.e. generic) and I have already done this, but I would now like to add further tools. 1) Genetic Algorithms ------------------------------------------------------- For this, I considered creating a scripting language, which described the object to be ''evolved'', and then described which parts of the object were variable (i.e. could change according to the GA), which parts were static (couldn''t change, such as a string which identifies the name of the object), the limits of the mutations (i.e. that a variable can only mutate between the values of 0 - 100), and then assignment of factors such as random seeds, the shape of a Gaussian distribution, certain functions (mathematical ones to calculate new variations) etc. 2) FSM''s ------------------------------------------------------- As far as I can tell, FSM''s are like nested If-Then_else blocks, and implementation of these into an object wouldn''t be worth much. Unless, we went with a kind of GUI builder tool, which allowed you to assign the states, the ''switching variables'' (ie conditions for changing state etc), and then order them as you wish graphically. Once designed, you could save it as a script, and then dynamically load it into the game, and provide pointers to the ''switching variables'', and variables affected by change of state. 3) PATHFINDING -------------------------------------------------------- I have no clue how to implement pathfinding in this generic sense, so any ideas would help! If anyone has any suggestions they would be welcome! Regards matt

You could have an A* search that searches a generic node tree,
Possibly use a template for nodes, or for the tree, so the user can use the tree/node interface to set pathcost and connectivity (rules). Probably have the user set the heuristic as a callback function, as well as having some generic heuristics, such as straight-line etc. that the user could use within certain guidelines. Sorry, not very detailed, but maybe it will help the idea''s engine

Hi! I think it''s pretty cool that you''re making an AI toolkit. I think that it might be useful now that these days developers are paying more attention to AI than they have in the past.

I personally am just beginning learning AI, but I did recently read an article by Steve Woodcock and at one point he listed a couple of features that he thinks would be useful for people to include in AI toolkits. He said pathfinding, FSMs, and FuSMs would be very useful. (FuSM = Fuzzy state machine).

About pathfinding, of course A* is the standard algorithm that everyone uses, but there are a ton of variations. You should probably research into it to find what''s best. From what I''ve heard, there are a couple of issues with usual pathfinding algorithms. One thing is that, even though it will give a mathematically correct answer, the movement of, say, a human does not look realistic. So there are some ways to fudge with the algorithm to make a smoother path.
Another problem is that if something is moving on a terrain which changes dynamically, the standard A* algorithm doesn''t handle this well. There''s an algorithm called D* that some people worked on, but I''m not sure if it totally solves the problem.
Also, in some games, even though the pathfinding is correct, there isn''t very good "traffic control". For example, let''s say some people are trying to cross a bridge, but the bridge is very narrow. Perhaps they will all run into each other and bump into each other, making a really big "traffic jam" and appearing to be really stupid. I think this also happens in "The sims". You can command your characters to walk through doors and things like that, but if another character is walking through the door at the same time, then they both just kind of stop and get confused- this can get really annoying.

Anyway good luck on your toolkit

Rajan

The problem you will have in fermenting large scale acceptance of an AI toolkit is that for most AI tasks, a domain optimised solution will always out-perform a generic solution. The trick is then to implement the broadest applicable library of functions that can be easily tuned and optimised. For example, one could easily design a GA to optimise a population of strings having an |x|y|z| chromosome structure, however, what if the values in x, y and z don''t use all of the bits in their data object, then there will be wasted computational effort in evolving the population. For instance, x might be a number between 1 and 6. Assigning it an unsigned char would be a waste of 1 bit and hence slow the algorithm down. Packing the bits for all variables into a shorter length string would remove wasted bits (at the small extra cost of having to pack and extract bits when encoding and decoding chromosomes.

This is just a simple example to highlight what I mean by domain optimisation of the solution algorithm.

Furthermore, don''t throw away the idea of implementing a FMS library. I think one of the best things that could be done for AI - particularly in games - is an XML-like interface for FSMs and FuSMs. The ability to graphically create these objects would really speed up development time. I wonder actually, are there any industry developers out there who work for companies that have already done this (written their own FSM editor)?

Just my $0.018 cents worth (deflation!),

Timkin

OpenAI is in fact doing the first two very well. Though it''s java, there shouldn''t be too much work in converting the code to C++.

You may even want to base your ideas on that, their GA+FSM project has a fair bit of maturity behind it.

Generic path-planning is a tough one, and this september it will have taken me a whole year of research to nail down (map learning + exploration + reactive/deliberative behaviour combination) I''ll let you know if it was worth while!

Btw, A* should crash and burn

Alex


Artificial Intelligence Depot - Maybe it''s not all about graphics...

Wow! I didn''t know you were clairvoyant Alex! ;0)

Can you predict when I''ll receive my last order from Amazon because they sure don''t seem able to tell me... ?



Stimulate

test