Steps for solve the mystery

Title of project:
Implicit coordination in distributed systems

Partners: Pierre Dillenbourg (TECFA), Ion Dumitrache (POLITEHNICA), Catalin Buiu (POLITEHNICA),
Cristian Ceconvciuc (POLITEHNICA)


1. A lot of talk...
2. First step: extract facts and goals from MOO answers and establish communication between Hercule and Sherlock
3. Herculog and Sherlog first version
4. Talk about co-ordination
5. Herculog and Sherlog second version
6. Herculog and Sherlog third version
7. Hercule and Sherlock found the criminal
8. Inferencing facts communication

1. A lot of talk... between Cristian CECONVCIUC and Catalin BUIU

 > >
> > About "Implicit Co-ordination in Distributed Systems" I talk with Pierre about meta-rules:
> > - rules who choose the strategy
> >   * by suspects
> >   * by questions
> > - rules who co-ordinate those 2 agents to communicate with the MOO medium or each with the other
> >   * location rules
> >   * sending important facts rules
> >   * asking for prove those important facts rules (trace of the inference)
>     One idea we must have in mind is that the 2 agents are not necessarily running on the same machine. What we do now is implemented on the same  machine for both agents. For example I am working on 2 versions of  co-operation:
> 1. A dumb Sherlog which only goes there and is speaking with Herculog giving some general indications. It might be viewed as a living version of the existing set of rules.
> 2. Exclusive solving and co-operation, where Sherlog takes a part of the task to solve, i.e. SherLOG tries to find the suspect who had the opportunity to take the run, while HercuLOG is doing the rest of the task.
    In this case there is no important which agent is running which machine, because all thing are happening via sockets; that's the motive for the agents can running on the different machine. You can try...    I think that Sherlog (1.) is just for beginning. I also make the same thing.    I also think that both agents must make approximately the same task (that's about strategy which both agents can approach, we can talk later about that). I mean finally the both agents must be able to find the criminal...

> Speaking about meta-rules, where to implement such rules?
> What about the coordination rules? Each agent should have a copy of these rules in his working memory?

    I think there are 3 types of rules: communication rules (between these 2 agents), strategy rules (what and how are doing each agent) and solved murder rules (which solve the murder, of course). There are many facts for each type of rules, which are changing between agents.

> >     I think that rules which are now asserted are too general or too large. For example when the agent decide to look, he >> looks in all rooms (the other agent in this time can interfere with the first agent). I
> That was a starting version and is implementing the simplest way of solving the mystery by ONE agent. When speaking > about TWO Agents we can think of what you are saying.
> I don't understand what exactly do you mean by "interfere", but this might occur (if you think about actions done by the both agents, like: they are both asking Oscar about last night) and we must not, in my opinion to restrict this possibility. Of course, the general idea would be to divide the job. And of course, we have to keep in mind, that doing something doesn't necessarily mean understanding that thing. I understood that our goal is to model the implicit coordination as it sometimes occurs between humans.

    I agree with that divide job in general and not be too restrictive, because in the future one artificial agent must be able to communicate with one human agent.

> > think that those "looks" must be done step by step: look in one room, find what the other agent make or send (maybe important facts). The same problem for asking about different objects: ask one suspect about it, then get some facts, make inference (with communication rules and resolve mystery rules), and then ask the same question another suspect.

> After the preliminary tests and observations we have to decide the general architecture, for working both on the same direction. All this sounds simple until we are in front of the Prolog environment.

OK. I will make the rules for that.

> >  What I made so far was it to resolve communication problems between the agent and MOO medium, because that function "sock_readln" it's blocked when there is nothing to read (it's attempting to read, but there is

> Yes, but the suspects will give the answers immediately as they receive the question.

I'm faster than the MOO environment. The sockets can keep information until I get them. You can try that, which I sent you.

> > nothing...). So I make one trick: before I loop reading I send myself one message, like: "page hercule #fact(stopread(HERCULOG))". When I meet this fact, I stop reading...

> And do what in the meanwhile?
> Unfortunately, this is not concurrent Prolog...

    I told you I'm faster than MOO. The cycle it's make instantaneously.

> About reasoning: it could be done:
> 1. as a set of facts is acquired (like now) - a methodic way;
> 2. or immediately after a new fact is obtained.
> I preferred the first version which is easier to implement.
> What do you suggest?

    I suggest new facts for those 2 types of rules: communicative rules and strategy rules. For the other type of rules I suggest some facts which can restricting those cycles (for example look in all room in the same cycle, ask all suspects about something in the same cycle, etc.), because if one agent make that, this agent can't be able to get new information, which can change the plans, from the other agent.

> >      I solved also a few design problems (when one fact was asserted I cannot read by words, only by ASCII code; etc.).

> This was not a problem. The program worked by reasoning on facts and not on Ascii codes. This is simply a problem of BinProlog predicates.
> >      All I need now to continue my work here is that verb from Janus (which is MOO programmer), the verb who answers to the agents in Prolog facts (with '&' character before one fact), and, of course, to find those meta-rules who co-ordinate the agents (in this case I will consult with all who are reading this mail).
> Waiting for your "consultation",
Me too, Cristian


2. First step: extract facts and goals from MOO answers and establish communication between Hercule and Sherlock

   The files qextract1.txt and qextract2.txt are 2 prolog sources examples for how the 'extract' function is working (it's about facts and goals extracting from the MOO answers; they are included support.txt file, which contain many helpful functions).

    At this time Sherlock it's connected as human, and must type just "page hercule #fact(start_com_hercule)" when receive one page from Hercule with fact(start_com_sherlock). That's means that communication between agents it's established.

 The agents at this step are working fine in main cycle (which is in the main program herc.txt or sher.txt), which is something like that:

Connect to the MOO
Page the other agent Bonjour...
Initialize the mystery
Read from the MOO (via socket)
Think (apply the rules)
Send information to the MOO ('advice' from the other agent, the movement commands - 'walk', or issue the commands from MOO - 'look', 'read', 'ask')
Read from the MOO (via socket)
steps 1 2 and 3 until solve the mystery (i.e. the agent find the criminal)
Report who is the criminal
Disconnect from the MOO


3. Herculog and Sherlog first version

    The first version of herculog and sherlog communicate via MOO between each other. It's an example how can they know which are visited what room. In this example I made the rules for movement in rooms, but step by step, and, except room 4 (which the agent begin to explore with), they not interacting in the same room.
    The agent program has the following files sources:

File (Hercule/Sherlock) Description / The main program / The 'think' function and 'qloopread(Q)' (first for apply the rules and second for read from the MOO via socket) / Communication rules / Strategy rules / Solve mystery rules / Facts knows apriori by the agents (like rooms, suspects, victim, etc.) Answers simulation from the MOO Different useful functions (like 'extrf', 'extra', etc.)
    New in this version:
- they're 2 distinguish files for (facts who are known at the beginning), because the order of the room it's different (for decreasing probability for meeting if they start at the same time).
- facts recognition from the other agent, via MOO.
- asserted the other agent facts and put them in the rules:
        * now both agents establish communication
        * now both agents know what rooms was visited by the other one
-the facts are preceded by '&' character because '#' in MOO it means something.


4. Talk about co-ordination (between Catalin BUIU and Cristian CECONVCIUC)

> >     In this case there is no important which agent is running which machine, because all thing are happening via socket that's the motive for the agents can running on the different machine. You can try...    I think that Sherlog (1.) is just for beginning. I also make the same thing.
> Are they maintaining a common knowledge base? if so, where do you keep it, if running on separate machines?

    Both agents keep their own database. They only exchange same data via MOO. The running on separate machine or the same machine idea is superfluous, because all things are happened via sockets (like telnet), so it's not really important which agent is where.
> > both agents must make approximately the same task (that's about strategy which both agents can approach, we can talk later about that). I mean finally the both agents must be able to find the criminal...
> >
> This is obvious, the problem is how to coordinate the actions and to model the implicit coordination. Please summarize your idea in a more logical way.

    I haven't a logical model for co-ordinate the actions of each agent. I'm working now at the communication technical problems (between agents and MOO and between each to other), because the model depends on the results which I'll get
them. For instance, I'm finished one variant of Hercule which is able to move, look and read in each room (step by step) and ask suspects about things, even it's appear a new one (when Hercule go to the bar, find that painting, so he must ask
suspects again, but about painting). I'll send you later this variant; I want to make it more "logical" :)


5. Herculog and Sherlog second version

    In the second version Hercule and Sherlock make the following steps:
- move in room 4;
- look in room 4, where they learn about new objects to ask (ski_jacket and gun; mona was implicit, also last_night) and new objects to look (mona, ski_jacket, gun);
- move each of them in different room, because for each room they send fact that they was there - that's for the first tour of rooms;
- for each room they can detect interest objects (to ask: painting, to look: painting, to read: sign, insurance_contract, registry, phone_log) and put the questions to suspects or look or read objects;
- Hercule walk from the lower corridor to the upper, and Sherlock upside down (I made that by changing again order of room in fact_?.pl files);
- the requests what_about(Agent,look/read,object,room) and did_you(Agent,ask,object) are made one per main cycle (where the agents are thinking, sending the advice and commands, and reading again maybe it's something from the MOO) (see example communication between Hercule and Sherlock);
- the number of facts who are sending to the other agent is limited at 5 per main cycle (for no congestion);

6. Herculog and Sherlog third version

 New in this version:
- I make difference between facts send by the MOO and send by the agents (in hercule_with.txt and sherlock_with.txt you can see ***F-MOO***>>> and ***F-AGENT***>>>, respectively);
- the agent memorize the answers from MOO;
- the agent answer at what_about(agent,M,X,R) other agent question (M could be 'read' or 'look', X is an object and R is room where the object is); in this case the agent give the MOO facts to the other agent;
- the agent answer at number(agent,ask,X,N,from,NS) other agent answer(X is an object, NS-total number of suspects); if N=0 the agent advice the other agent to ask about X, if N=NS the agent send fact(good(ask,X)), if N<NS-N (N<NS/2) the agent send fact(keep(ask,X)) (see example communication between Hercule and Sherlock);


7. Hercule and Sherlock found the criminal

    Finally I finished one variant of artificial agents who solved the mystery. I had some problem with Prolog memory, because there are many facts asserted who keep memory space occupied, but I found a solution for that :) (I allocated more memory for both agents and I used some Prolog instructions who minimized the memory space and also I allocated more less goals for the agents - it seems that they keep a lot of memory and there is some kind of restrictions for goals).

 New for this version:
- after first tour (when the agents don't see each other) they put questions to each other like
   * did_you(agent,ask,about,X), where X is an object to ask: the other agent answer number(ask,X,N), where X is an interesting object to ask and N - number of suspects who was asked: the answer at the answer could be: object(agent, X), if N=0, keep(agent,ask,X), if N<NS-N (NS is total number of suspects) or good(agent,ask,X) if N=NS; this question appear after first tour;
   * what_about(agent,M,X,R), where M could be 'read' or 'look', X is an object to 'read' or 'look' and R is the room where the objects is: the answer is answ_ag(agent,M,X,R,A), where A is the answer from the MOO: in that way the agent who receive that can assert MOO facts via the other agent; but only one for each type per main cycle; this question appear after first tour;
- the agents give some statistical data at the end of running;
- the agents know to answer at give_facts_nr(monitor) and give_goals_nr(monitor) questions: the answer could be number_facts(agent,N) or number_goals(agent,N): they have up to 450 facts and 10 goals (see monit_hf_ss.txt or qout1_hf_ss.txt);
- the agents send the follow facts when they're inferencing:
   * kill_reason(agent,T,P): where T could be 'money', 'work' or 'love' and P is some kind of probability (between 0 and 1):
   * find_has(agent,X,H,T,1): X is a suspect, H could be 'motives', 'opportunity' or 'weapon', T could be 'work', some time, 'love', or 'access'; this is the fact who increase the guiltiness score; (see example communication between Hercule and Sherlock).
- I made a small programs in C/UNIX for extract from monitor log only
   * communication part between agents ('page' commands);
   * movement and investigate part for the agents ('walk', 'look', 'read' and 'ask' commands).

    The number of rules are 96 right now.


8. Inferencing facts communication

Cristian Ceconvciuc  

Last updated: Dec. 16, 1997