# An Abstract Framework for Non-Cooperative Multi-Agent Planning
## 5 Case Study
### Strategic Planning  
The strategic planning phase involves two systems. On the one hand, we use best-response dynamics to manage the strategic behavior of the agents, allowing them to make their proposals until a convergence point is reached, which is by definition a Nash equilibrium. On the other hand, each agent is provided with a CBP system that allows him to obtain plans to solve the problem based on past experiences. In the following, we explain how both systems are used in this case study. An arbitrary order is chosen among the truck agents. Let's assume the order is A, B, and C, for simplicity. Then, each truck agent, in turns, proposes, by retrieving a plan \(\pi\) from its case base, the best plan to solve his goals considering the plans of the other agents (if any). This means that the plan of an agent can affect another if there is any congestion that may decrease the expected utility because the cost of the simultaneous use of a road is increased (i.e., fuel/battery consumption increases and/or travel time increases). The best-response dynamics process takes place as follows:  
1. Agent A retrieves the case/plan \(\pi_{A1}\) that best matches with the problem to solve with a similarity of 92%. The past case match with the current problem of delivering package \(p_{1}\) since the origin and destination are almost the same with a slight deviation. Since there is no agent who has proposed his plan yet, there is no interaction, so, for agent A, this extracted plan is his best option. \begin{table}
\begin{tabular}{c c c c} \hline \(c(ag_{i},p_{j})\) & \(p_{1}\) & \(p_{2}\) & \(p_{3}\) \\ \hline A & 10 & 21 & 16 \\ B & 14 & 9 & 17 \\ C & 18 & 19 & 12 \\ \hline \end{tabular}
\end{table} 
Table 1: Costs of each agent \(ag_{i}\) to deliver each package \(p_{j}\). Agent B also retrieves the best plan/case \(\pi_{B1}\) to solve his goal with a similarity degree of 95%. However, this plan introduces a congestion with the current plan \(\pi_{A1}\) of agent A for the simultaneous use of a road (see the rectangle area of blue and red lines in Figure 4 where the paths of both trucks can overlap). Although agent B is causing a congestion that reduces the expected utility to both agent A and agent B, plan \(\pi_{B1}\) still has more utility than the next alternative \(\pi_{B2}\) in his case base because it has a longer path at a higher cost. Thus, from a rational point of view, agent B prefers \(\pi_{B1}\) in congestion rather than another lower utility alternative that avoids congestion like \(\pi_{B2}\). 3. Agent C retrieves the best plan \(\pi_{C1}\) of his case base to solve his goal of delivering package \(p_{3}\) with a similarity of 100%. Since agent C does not have any interaction with the other agents, he can apply his plan with the expected utility, while also not affecting the utility of other agents. 4. Agent A analyzes its current proposed plan \(\pi_{A1}\) which is affected by a congestion with agent B for the simultaneous use of a road. Using his CBP system is able to retrieve another case/plan \(\pi_{A2}\) with a similarity of 89% to the current problem to solve, which is lower than the similarity of \(\pi_{A1}\) (92%). However, the similarity only refers to how similar one case is to another, but does not take into account how another agent's plan may affect it (i.e., congestion interactions). Therefore, although the new case \(\pi_{A2}\) with a similarity of 89% may have a lower utility a priori, it is actually higher than the utility of the previous plan \(\pi_{A1}\), since, in that case, this utility is affected by the congestion and ends up being lower. Thus, agent A changes his proposed plan from \(\pi_{A1}\) to \(\pi_{A2}\), with a slightly higher utility, which is in this moment his best response. 5. Agent B analyzes his current plan \(\pi_{B1}\) and realizes that the congestion that existed with agent A has disappeared because agent A has changed his plan. Thus, the utility of \(\pi_{B1}\) has increased slightly with respect to the previous iteration.