# Multi-Agent Chronological Planning with Model-Agnostic Meta Reinforcement Learning
## 3 Methods
### Chronological Planning Problem Formulation  
We consider a multi-agent chronological planning problem in a navigation task with precedence constraints, where agents autonomously plan their routes toward their targets in a specific chronological order. There are \(N\) agents and \(N\) landmarks in our scenario. The task is to navigate the \(N\) agents to occupy all the \(N\) landmarks in an order and simultaneously avoid collisions with each other. At the start of each episode, the positions of both agents and landmarks are randomly reset. Moreover, we have excluded generated positions where any two landmarks are too close, preventing unavoidable collisions when the agents are approaching their destination. A simple example is shown in Figure 1. In addition, the precedence constraint requires that agents must occupy the \(N\) landmarks in a certain order. An agent can access the position and velocity of itself, as well as the positions of other agents and all the landmarks. Each agent can also observe whether each landmark is occupied. As the agents in our scenario must consider the interaction with other agents when planning the routes (i.e., making decisions), we use stochastic game (SG), also known as Markov game, to describe the multi-agent decision-making process in our problem. A stochastic game can be regarded as a multi-player extension to an MDP, which allows agents to move simultaneously [51]. The stochastic game of our problem is defined by the number of agents \(N\), the state set \(\mathbb{S}\), the action sets \(\{\mathbb{A}^{1},\mathbb{A}^{2},\ldots,\mathbb{A}^{N}\}\), and the observation sets \(\{\mathbb{O}^{1},\ldots,\mathbb{O}^{N}\}\). For each agent \(i,o^{i}\in\mathbb{O}^{i}\) is an observation of the global state \(s\in\mathbb{S}\). In our scenario, \(o^{i}\) contains the absolute position and velocity of the \(i\)-th agent itself and the relative locations of all the other agents and landmarks. For the sake of universality and reasonability, we define the global state \(s\in\mathbb{S}\) as the combination of observations from the \(N\) agents, \((o^{1},\ldots,o^{N})\), where \(o^{i}\in\mathbb{O}^{i}\). To describe the environmental dynamics, state transition \(P(s^{\prime}|s,\mathbf{a})\) gives the distribution of the next state \(s^{\prime}\) when taking a joint action \(\mathbf{a}=(a^{1},\ldots,a^{N})\) under the current state \(s\), and per-agent reward function \(R(s,\mathbf{a},s^{\prime})\) returns a scalar value for agent \(i\) for a transition from \((s,\mathbf{a})\) to \(s^{\prime}\). Our reward function will be explained in detail in Section 3.2. The policy of agent \(i\) is represented by \(\pi^{i}=P(a^{i}|s)\), which gives the action probabilities with regard to a given state and we denote the joint policy of all the \(N\) agents by \(\mathbf{\pi}=(\pi^{1},\ldots,\pi^{N})\). Figure 1: An illustrative case of our problem. The numbers inside landmarks indicate the order in which to occupy them. In a stochastic game, the goal of each agent is to find a behavioral policy \(\pi^{i}\) that can take sequential actions at every step \(t\) such that a discounted cumulative reward in Equation (1) is maximized, where \(\gamma\) is the decay factor. Here, we use the superscript of \((\cdot^{i},\cdot^{-i})\) to distinguish between agent \(i\) and all the other \(N-1\) teammates. In \((\pi^{i},\pi^{-i})\), the former item means the policy of agent \(i\) while the latter one means the joint policy of all the agents except agent \(i\). \[V^{\pi^{i},\pi^{-i}}(s)=\mathbb{E}_{s_{t+1}\sim P(\cdot|s_{t},a_{t}),a^{-i} \sim\pi^{-i}(\cdot|s_{t})}\left[\sum_{t\geq 0}\gamma^{t}R_{t}^{i}(s_{t},\mathbf{a}_{t },s_{t+1})\mid a_{t}^{i}\sim\pi^{i}(\cdot\mid s_{t}),s_{0}.\right] \tag{1}\]  
As shown in Equation (1), the optimal strategy of each agent is not only determined by its own policy \(\pi^{i}\), but is also affected by the joint policy of other agents in the environment \(\pi^{-i}\).