Cooperative Problem Solving (CPS)
CPS provides a framework for teamwork among a group of agents. Wooldridge & Jennings (1999) give a description of CPS which consists of a model of four consecutive stages. The stages are recognition, team formation, plan formation, and execution. At every stage one agent of the group acts as an initiator, communicating with the other agents of the group.
A CPS process begins at the potential recognition stage when some agent recognizes the potential for cooperative action. We will refer to this agent as the initiator. At the next stage, team formation, the initiator asks for assistance from other agents. When this stage is successful, it will end with a group of agents having some kind of general knowledge of all members the team consists of (and having some kind of nominal commitment to collective action). At the third stage, plan formation, the team will come to some agreement about the exact course of action they will follow. The fourth and last stage, called the team action stage, consists of the team performing the action they agreed on (Wooldridge & Jennings, 1999).
At the first stage, the initiator communicates one-on-one with agents to see if he thinks they are capable of solving the problem. With each agents he has a conversation, a dialogue. In the second stage, the initiator has dialogues with agents to determine whether or not they are willing to become a member of the team to solve the problem. When this has succeeded, he transmits a group message, informing all agents about who the group members are. The second phase is now completed. After this group message, other agents may bid to become initiator. An initiator change can occur after that. In the third stage multiple dialogues, group messages and initiator switches may occur. This is because the third stage consists of several substages. In the first substage, the task at hand is divided in subtasks by the initiator. He uses dialogues with all agents to establish this. When it succeeded, a group message follows, after which an initiator change may occur. In the second substage the (new) initiator will assign actions to the subtasks. When this succeeds, another group message follows, after which, again, an initiator change may follow. In the third and last substage, the actions to be performed are allocated to agents. When this is done, all agents are informed of who has to do what with another group message. In the fourth and final stage, all agents perform their task.
It is clear that a protocol for CPS needs to provide the possibilities for one on one dialogues, for group messages, and for initiator changes. Because all these occur in the second and third stage of CPS, in our simulation we focused on these two stages.
At this point we should make clear that a protocol for a CPS process is a high-level protocol which can be built on top of low-level protocols TCP (one-on-one) and multi-agent TCP (one-on-group). In a CPS process, a package can be seen as a complete tape sent from a sender to a receiver with appropriate low-level acknowledgements. The same applies to acknowledgement messages. We refer to Freek Stulp's knowledge-based one-on-one simulation for clarification. In our simulation, we do not deal with tapes, but with messages. We assume that safety and liveness holds. This is guaranteed by the low level transmission protocols we could use. This means that in our CPS simulation, we do not know exactly when our messages will arrive, but we know that they will at some point. We implemented this by letting messages travel at different speeds.
In the next section, we will go into more detail about the communication protocol for CPS described in Van Baars & Verbrugge (2007).
