# A Social Multi-Agent Cooperation System Based on Planning and Distributed Task Allocation
## 5 Distributed Task Allocation
### The Principle of Distributed Task Allocation  
To ensure distributed task allocation, we define two kinds of planning agent:  
* Initiator: the planning agent that requests help to perform its task;
* Participant: the planning agent having the requested resources that receives the announced task and sends back its response.  
To ensure the coherent behavior of the planning agent, we propose two possible states, i.e., States = {BUSY, IDLE}. Whenever a planning agent is an initiator, the planning agent state should be BUSY. We consider a planning agent in an IDLE state when it is free, i.e., when it has no task to do. We suppose that only an IDLE planning agent can be assigned to a new task as an initiator or as a participant.  
The idea of the algorithm is illustrated as follows.  
* The initiator agent, denoted as _InitA_: the planning agent that starts the distributed task allocation process. There are many reasons to apply a distributed task allocation in the whole system such as the fact that the planning agent is unable to execute a task by itself, it is too busy, or it does not have all the necessary resources. Each initiator agent InitA has a list of planning agents. It sends a request to the planning agents: Resource_Announce_Message = <AgentID, TaskID, Resource(_number_)>, containing the initiator agent identity, the task identity and the number of requested resources.  
The initiator agent waits for the response from the other planning agents.  
The planning agent (called the participant agent) receives the message _Resource_Announce_Message_ sent by the initiator agent _InitA_; it checks the possibility of applying distributed task allocation based on its state. If it is feasible (i.e., the participant agent has the requested resources and is idle), it accepts the collaboration with the initiator agent. If the participant agent is busy, it refuses the request.  
If the participant agent _Aj_ is IDLE then it provides data regarding its identity, the types of resources it owns and the executing time, explicitly, Propose_Message = <AgentID, Resource, Execute>.  
If the participant agent _[PERSON]_ is BUSY then it sends a negative response containing the following message Refuse_Message = <AgentID>.  
After collecting the responses from all the participant agents or the timeout is over, the initiator agent InitA then compares the available resources from these participant agents with the resources required for its task _tInitA_. This leads to two cases:  
If the initiator agent InitA obtains all the requested resources then the initiator agent sends a notification message to the selected participant agent Aj. The initiator planning agent waits for a confirmation.  
Two cases can happen depending on the selected participant agent Aj state  
If the selected participant agent Aj is still free, it sends a confirmation message to the initiator agent InitA and its state will be changed to BUSY: Confirm_Message = <AgentID>. Consequently, the distributed task allocation protocol finishes well.  
If the selected participant agent Aj becomes busy (which means it receives a notification message from another initiator), it sends a decline message to the initiator agent InitA: Decline_Message = <AgentID>. Therefore, the initiator agent InitA repeats the same steps from the beginning.  
The different distributed task allocation steps are illustrated in Figure 3, where nbR represents the number of participant agents related to the initiator agent InitA.