# UAV Formation Shape Control via Decentralized Markov Decision Processes
## 2 Problem Formulation  
**Unmanned aerial vehicles:** We consider quadrotor motion dynamics in 3D, as modeled in [34; 35]. In this study, our goal is to optimize the _waypoints_ (position coordinates in 3D space) for the quadrotors to guide the UAVs to their destination formation shape while avoiding collisions. **Communications and Sensing:** We assume that UAVs are equipped with sensing systems and wireless transceivers with which each UAV learns the exact location and the velocity of the nearest neighboring UAV. Our decentralized control method requires only the kinematic state (location and velocity) of the nearest neighbor to optimize the control commands of the local UAV. **Objective:** The goal is to control the swarm (optimizing _waypoints_) in a decentralized manner, such that the swarm arrives at a certain pre-determined 3D geometrical surface in the shortest time possible while avoiding collisions. We formulate the swarm formation control problem as a decentralized Markov decision process (Dec-MDP). Dec-MDP is a mathematical formulation useful for modeling control problems for decentralized decision making. This formulation has the following advantages: (1) allows us to efficiently utilize the computing resources on-board all the UAVs, (2) requires less computational time compared to centralized approaches, (3) as UAVs are decentralized, point of failure of the entire mission is minimal, (4) decentralized approach provides robustness to addition or deletion of UAVs to the swarm, (5) UAVs do not need to rely on a central command center for evaluating optimal control commands. We define the key components of Dec-MDP as follows. Here, \(k\) represents the discrete-time index. Dec-MDP Ingredients**Agents/UAVs:** We assume there are \(N\) UAVs in our system. The set of UAVs is given by an index vector \(I=\{1,...,N\}\). This index vectors may be referred to as a set of agents or set of independent decision makers. Here, a UAV can be considered an agent or a decision maker. **States:** We model the system dynamics in discrete time, where \(k\) represents the time index. The state of the system \(s_{k}\) includes the locations and velocities of all the UAVs in the system. **Actions:** The actions are the controllable aspects of the system. We define action vector \(a_{k}=(a_{k}^{1},\ldots,a_{k}^{N})\), where \(a_{k}^{i}\) represents the action vector at UAV \(i\), which includes the position coordinates in 3D for the UAV. **State Transition Law:** State transition law describes how the state evolves over time. Specifically, the transition law is a conditional probability distribution of the next state given the current state and the current control actions (assuming the Markovian property holds). The transition law is given by \(s_{k+1}\sim p_{k}(\cdot|s_{k},a_{k})\), where \(p_{k}\) is the conditional probability distribution. Since the state of the system only includes the states of the UAVs, the state transition law is completely determined by the dynamics of the UAVs (discussed in the next section). In other words, the transition law is given by \(s_{k+1}^{i}=\psi(s_{k}^{i},a_{k}^{i})+\mathcal{W}_{k}^{i},i=1,\ldots,N\), where \(s_{k}^{i}\) represents the state of the \(i\)th UAV and \(a_{k}^{i}\) indicates the local dynamic controls (position coordinates) of \(i\)th UAV, \(\psi\) represents the motion model as discussed in Section 4, and \(\mathcal{W}_{k}^{i}\) represents noise, which is modeled as a zero-mean Gaussian random variable. **Cost Function:** The cost function \(C(s_{k},a_{k})\) deals with cost of being in a given state \(s_{k}\) and performing actions \(a_{k}\). Here, \(s_{k}\) represents the global state, i.e., the state of all the UAVs in the system. Since the problem is decentralized, each UAV only has access to its local state and the state of the nearest neighboring UAV. Let \(b_{k}^{i}=(s_{k}^{i},s_{k}^{nn})\) represent that local system state at UAV \(i\), where \(s_{k}^{nn}\) is the state of the nearest neighboring UAV, and \(nn\in I\backslash\{i\}\).