# Three-Dimensional Multi-Agent Foraging Strategy Based on Local Interaction
## 4 Assumptions and Notation  
We consider discrete-time systems. Let \(dt\) define the sampling interval in a discrete-time system. For instance, in the case where our controls are applied at every 2 s, \(dt=2\) seconds. Consider the case where the 3D workspace is closed and bounded. There are unknown obstacles inside the 3D workspace. Suppose that there are initially \(N\) agents at the base. Let \(n_{i}\) define the \(i\)th agent (\(i\in\{1,2,\ldots,N\}\)). Let \(\mathbf{n}_{i}\in\mathcal{R}^{3}\) define the 3D location of \(n_{i}\), where \(i\in\{1,2,\ldots,N\}\). Let \(\mathbf{n}_{i}(k)\in\mathcal{R}^{3}\) indicate \(\mathbf{n}_{i}\) at sample step \(k\). The sampling interval between sample steps \(k\) and \(k+1\) is \(dt\) seconds. Because the 3D bounded workspace contains unknown obstacles, it is not possible to derive the number of agents required to cover the entire workspace. Thus, we assume that  
Figure 1: Tree illustration with \(c(v)\) and \(p(v)\). \(N\) is sufficiently large to cover the entire workspace. Section 5.1.3 handles the exceptional case in which \(N\) is not sufficiently large to cover the full workspace. The motion model of each agent \(n_{i}\) is  
\[\mathbf{n}_{i}(k+1)=\mathbf{n}_{i}(k)+\mathbf{v}_{i}(k)\times dt. \tag{1}\]  
Here, \(\mathbf{v}_{i}(k)\) defines the velocity of \(n_{i}\) at sample step \(k\). In our paper, each agent moves based on local interaction with its neighbors. Section 5.3 presents how we set \(\mathbf{v}_{i}(k)\) in this paper. The motion model in (1) has been widely applied in the literature on multi-agent controls [29; 30; 31; 32; 33; 34; 35; 36; 37]. Let \(MaxS\) define the maximum speed of \(n_{i}\). This implies that \(MaxS\geq\|\mathbf{v}_{i}(k)\|\) for all \(i,k\). We acknowledge that (1) does not consider the motion constraints on an agent. Our paper is based on generation of multiple agents' paths, i.e., weconsider high-level control of multi-agent systems. For instance, consider an agent such as an Autonomous Underwater Vehicle (AUV) with non-holonomic constraints. Along the generated path, each end point of a straight line is set as the waypoint for an agent. With the waypoints set, we can utilize the path following controller in [38; 39] while considering the dynamics of the agent to ensure that an agent visits the waypoints. How to ensure that an agent with motion constraints move along the waypoints is beyond the scope of the present paper. Let the _sense-communicate range_\(r^{cs}\) be defined as the smaller value between the maximum sensing range and the maximum communication range. According to this definition, if \(\|\mathbf{n}_{i}-\mathbf{n}_{j}\|<r^{cs}\), then \(n_{i}\) and \(n_{j}\) can sense each other while communicating with each other. We say that a puck is _detected_ by \(n_{i}\) in the case where the relative distance between a puck and \(n_{i}\) is less than the sense-communicate range \(r^{cs}\). Therefore, our aim is to ensure that every puck is within a distance \(r^{cs}\) from at least one agent. In this way, every puck can be found by the deployed agents in a provably complete manner. Let \(L(\mathbf{n},\mathbf{m})\) define a straight line segment with the two end points being two agents, say, \(\mathbf{n}\) and \(\mathbf{m}\). We say that \(L(\mathbf{n},\mathbf{m})\) is _collision-free_ when \(L(\mathbf{n},\mathbf{m})\) does not cross an obstacle. This implies that an agent can safely travel along \(L(\mathbf{n},\mathbf{m})\) without colliding with any obstacles. Let \(I=(V(I),E(I))\) define the graph presenting the networked system. Every node in \(V(I)\) indicates an agent. An edge, say \(\{n_{i},n_{j}\}\in E(I)\), indicates that \(n_{i}\) and \(n_{j}\) are neighbors. Here, we say that two agents \(n_{i}\) and \(n_{j}\) are _neighbors_ in the case where the following conditions are met:  
1. \(L(\mathbf{n}_{i},\mathbf{n}_{j})\) is collision-free;
2. \(\|\mathbf{n}_{i}-\mathbf{n}_{j}\|<r^{cs}\), i.e, \(n_{i}\) and \(n_{j}\) can sense each other while communicating with each other.