# A Social Multi-Agent Cooperation System Based on Planning and Distributed Task Allocation
## 2 Related Work  
Task allocation is considered as a problem of allocating autonomous agents to a set of tasks having some specific properties such as priority, execution time, constraints, etc. When an agent Agi has a task and cannot execute it properly, then the agent Agi tries to find other agents that can execute this task and assigns the task to a particular one. According to [24], the tasks in the multi-agent system can be categorized into the following classes:  
1. Spatially organizing behavior: in this system, the agents interact among themselves to execute a spatial configuration and have minimal interaction with the environment;
2. Collective explorations: in this system, the agents focus rather on interacting with the environment than among themselves;
3. Cooperative decision making: in this system, the agents interact among themselves as well as with the environment to complete a complicated task. In this paper, we are interested in cooperative decision making, which can be divided into three categories: centralized, distributed or combined task allocation approaches. The centralized task allocation approach is characterized by a top-down hierarchical topology where a central server plays a particular role as a coordinator between all agents (like in the blackboard model) [25]. This solution achieves the best possible task allocation solution, but it is not suitable for a large scale of tasks due to the huge computation in the server. The distributed task allocation approach means that all the agents must cooperate together to find a convenient task allocation solution in the whole system [26; 27; 28]. It is considered as a solution to avoid the risk of central server deficiency (i.e., each agent is completely autonomous from the other agents). This solution is more scalable and robust but raises the communication overhead of the agents. A combined task allocation approach benefits from the two precedent solutions, which means it uses centralized information and does not have any point of failure. However, this solution is not easy to implement and can only be applied to a very specific system (such as a manufacturing system). In this work, the distributed task allocation approach is adopted. However, our method is still valid for a centralized solution. Many solutions have been employed in distributed task allocation such as the market-based approach, the contract net protocol (CNP), threshold-based algorithms, coalition formation and teamwork. The market-based approach [29] uses a market-like mechanism where the consumers get the resources needed after negotiation with the providers. This solution is good, but it differs from our solution as it leads to a huge number of exchanged messages due to a large number of providers. The contract net protocol [30; 31] is well used, especially in a multi-agent system. The principle is imitating the economic behavior of the \"announce--bidding--award\" mechanism. It is based on four steps: (1) task announcement--when an agent needs a task, it announces it to the others (called auction agent); (2) task bidding--the other agents send their proposal to the auction agent; (3) evaluation and selection--the auction agent selects the optimal proposal; and (4) task execution--the auction agent sends a notification to the selected agent. Though this solution is easy to implement, our solution is better as the agents can join or leave the system during the negotiation (the CNP does not allow this modification during the running of the algorithm; that is why the algorithm should be re-executed and would never give results if the modification rate was high). The second advantage of our solution is reducing the number of involved agents. The threshold protocol [32] was inspired by the biological behavior model of insect colonies. An agent accepts the execution of a new task when it compares an environmental stimulus for the task with some internal preference for the task type and finds it similar.