quote:

---

Original post by phemmer

Hi bishop_pass,

first of all i think we are on the right track now. I hope the others do not mind if we discuss that kind off hardcore stuff here, but i would say we should try to make the discussion understandable for all which are really interested.

Totally agreed, since what we want to achieve is something practical. We can try to prove things afterwards as a nice excersise, but it is not neccessary since there is enough literature that tells us what we can achieve and what the pitfalls are.

The only thing i am missing at the moment is the use of:
For all "\-/" and Existence Quantors in your formulas, but i think we will also find a common level here. I say this because there is another normalized form of such formulas that cleans up
those stuff; i mean Praenex formulas.

If you don''t mind i would like to agree about some more things:
First of all we should agree on how to write the different mathematical signs. Since we cannot use MathML we should use normal ASCII character set. Or do you have any better idea ?
Then we verbally should describe some test cases and try to formulate them in a syntax to be defined. That means let us create a world scenario (simple J&R, RTS, RPG) and try to describe it using our future rule set definitions. Let us instantiate some objects and look how far we come with our first model. I want to get a feeling for:
How to write rules, how to process state changes, how to use them in a game engine etc.

---

phemmer,

First of all, could you make an effort to isolate your statements from the quoted body of my statements by using the quote tag. I almost miss some of the thngs you say because they are reduced in font and mixed in with my quotes. Likewise others are probably missing what you are saying. And lastly, it can look like I said what you said instead of you saying it.

Regarding the other stuff, since I have not yet talked about existential quantification, all variables have been implicitly universal. As for syntax, despite Apex''s suggestion that I use a ''v'' for OR, I have been using an ''|'' as it is generally understood to mean OR around here.

So I have the follwing syntax:

& = AND.
| = OR.
CAPITAL LETTER = literal or atom.
small letter = varaible.
(Ax,y,z) = universal quantification of the variabls x, y, z.
(Ex,y,z) = existential quantification of the variables x, y, z.
f(P,x) = a function with args, in this case, a constant and a variable.
A -> B = logical implication where A implies B.
A <- B = logical implication where B implies A.
A <-> B = bidirectional implication where A implies B and B implies A.
~A = NOT A meaning A is NOT true.

quote:

---

Original post by Krippy2k

Hey Bishop

I just wanted to say that I think what you are working on is very interesting and would definitely have an impact on the gaming world as computer power gets healthier.

I was working on some similar projects for AI in VR for the DoD a few years back and I still explore the problems with my old colleagues occasionaly. It has been a while though. Although I cannot disclose any of the specific AI logic that was used I am under no restrictions for discussing the theory behind it.

I don't have much time right now but I will try and come back later or tommorow and post some more on the subject. But basically we had 6-way logic which I will call: Yes, No, Dont Know, Dont Care, Might Be(%) and Irrelevant.

These would be further refined depending on the importance of the agent in question. An infantryman would not need as much complexity as the commander of an aircraft carrier.

As the importance grows you need to not only understand what the agent knows but what the agent thinks he might know and what he really wants to know.

I am not much into spewing mathematical equations but I can discuss it in english Or code. I am working on a game right now and I am just learning how to use OpenGL and D3D pretty good. Then I will start working on some cool AI and could always use a healthy discussion.

Seeya
Krippy

---

Krippy, that is very interesting. And I agree that it is desirable that an agent knows what he knows, and be able to reason about the fact that he knows that he knows something. I have not necessrily addressed the subtle aspects of that, but I agree it is significant.

Hope to hear back.





Edited by - bishop_pass on June 10, 2001 12:51:11 PM

Well, I possibly made an intuitive leap today and devised a data structure which (I am pretty sure) reduces the graph search to a matter of classifying the two ends into a set which contains the two. And the best part (or the part which makes it useful) is the fact that the data structure only requires about twice the storage of the original graph.

The whole idea relies on the system doing a case by case analysis of each predicate definition and determining the type of relation is actually there. For example, there are:
recursive relations
chained relations
circular relations
generalized relations
etc.

I haven''t really looked at all of them. But I have figured out the basic recursive relation and the data structure which makes the search very tractable. I hope that most all definitions fall into some type of classifiable method where the system can choose an appropriate data structure for it.

If this works, then high speed is a possibility. But I haven''t really looked ahead to how this might work for function unification yet.

quote:

---

Original post by bishop_pass

Imagine a graph of nodes and links between the nodes. The nodes don't have any spatial dimension, merely information regarding their connections to other nodes. Each link is categorized as a type of link, in this case, the predicate the link represents.

---

quote:

---

Here are the standard graph search methods: depth first, breadth first, iterative deepening, and bidirectional breadth first. I am leaning towards bidirectional breadth first with the intention of the variable bindings meeting in the middle and taking the intersection to determine if there is a connection. And I believe I have come up with a very fast way to do it with bit arrays.

---

I just realised that a simple search will work even without monster processing power. The maximum complexity is the number of nodes multiplied by the number of links in the proposition being solved (with each new link, all the nodes must be considered again). I thought that it would be a huge exponential backtracking, but since you only need to find but one path, it works in polynomial time.



As for the search method, since there is no optim path you need to consider, a best first (A*, branch and bound, whatever, I forget the exact definition) algorithm should work better. Still, if no path exists any graph-search will have to just expand through the whole search space.


So, I thought about finding a way to estimate how likely is it for a certain node to be found on a correct path on a certain position (the probability for a certain node to be unified with a certain variable). If I can do this, I can expand the most likely nodes first. In a thorough search, if no path is found, I can always come back to the less probable ones. Or I can just expand a maximum number of nodes, and if no path is found, the program can just answer "I dont think this is true" instead of "This is false".

To solve an A | B | C | D proposition, I think it would be better to expand say 1000 nodes for A, then 1000 for B, and so on. The advantage is that if any of A,B,C,D is true, chances are it will be solved without fully expanding all the search spaces of the false predicates of A, B, C, D. However, if all are false, for 100% accuracy, the algorithm has got to search through all the search space. Again, it can trade 100% accuracy for speed.


I thought of creating an dual database (called database2, and its nodes are called nodes2; likewise, the initial knowledge base is called database1 storing info about nodes1). This database2 will have very few nodes2 (ie. 100 times less than the nodes1 in the database1). Each node2 of the database2 will represent a category of nodes1 in the large database1. A node1 in the database1 can fall into more categories - it can be represented by more nodes2.

The database2 is not a standard knowledge database. It stores statistical information about the database1.

Each node2 in the database2 will store :
- the number of nodes1 from database1 that fall in this categ.
- for each type of link L and each two nodes2 A and B, the database2 will know how many nodes1 y represented by the B categ are linked by nodes1 x in the A categ (how many y nodes1 in B categ exist so that L(x, y) is in database1 and x is a node1 in the A categ).


Using this dual database the probabability I need can be calculated very fast with simple expanding through the database2, very similar with the expanding in the database1. This expanding will be very fast, depending on the number of nodes2. The number of nodes2 can be used as a tradeof between the accuracy of this probability calculation and the time needed.


I am worried though that some special nodes1 that fall into a category but are different in some way from its category will be thrown away along with its category. I propose that all the nodes1 that are different from all the categs they fall into by a certain predicate (ie a magic horse that can talk) be considered special and always expanded when the kind of predicate that makes them different is reached (ie when the program must expand the nodes1 that can talk, the database2 will recomend humans, elfes and dwarves, but before these, Quitam the talking horse will be expanded - he is a talking exception).



I'm not very sure wether this can work, nor about the exact implementation...

Edited by - Diodor on June 16, 2001 11:54:41 AM

Diodor, I''m really impressed with the thought you''ve put into the problem. What you are describing is meta-level data about the knowledge base, and possibly some sort of pre-compilation of certain features of the knowledge base.

I haven''t completely digested what you have said though. Could you draw a picture, scan it, and put a link to the picture? I''m thinking of a type of picture where the nodes are lttle circles and the links are lines connecting the nodes.

Or, could you at least describe a very small knowledge base (in words, at least) and then fully describe database2 and how it works in relation to database1.

[Regarding the last post I made above, I must update that I have since shown that it would not always be linear in size as I thought. Certain cases would cause an exponential growth in size. (And possibly search time)]

One possible train of thought I have had is the automatic classification of whether predicate definitions are recursive or not, and adopting a policy of caching those predicates which are not, and adopting a some other poicy of effecient inference on the recursive ones.

For example, look at these definitions:

Parent(x,y) <- Father(x,y)
Ancestor(x,y) <- Parent(x,y)
OlderThan(x,y) <- Ancestor(x,y)

All of these definitions are rather simple, so why not just cache the values? In other words, do a forward type of reasoning at assertion time. So, if we assert:

Father(Bob,Bill)

Since the system has preflagged this predicate definition as one to cache, we automatically assert:

Parent(x,y)
Ancestor(x,y)
OlderThan(x,y).

This produces extra data, (but it is a linear increase) and it makes it unnecessary for the system to expand OlderThan to Ancestor at inference time.