# Three-Dimensional Multi-Agent Foraging Strategy Based on Local Interaction
## 5 3D Multi-Agent Foraging Strategy
### Provably Complete Puck Search
#### 5.1.2 Distributed Puck Search Protocol
Algorithm 3 iteratively appends a parent node to \(P\) until \(n_{1}\) receives \(P\). Because \(n_{i}\) is initially a neighbor to \(n_{1}\), the path information \(P\) is transmitted to \(n_{i}\). ```
The agent \(n^{\prime}\) broadcasts \(P=\{n^{\prime}\}\) to its parent \(p(n^{\prime})\) in \(T\); repeat if an agent \(n\) receives the path information \(P\)then \(P.append(n)\); \(P\) is transmitted to \(p(n)\); endif until\(n_{1}\) receives \(P\);  Return \(P\);
```  
**Algorithm 3**\(P=path(n_{1},n^{\prime})\)  
In Algorithm 2, \(n_{i}\) travels along the path in \(T\) to reach \(n^{\prime}\). For convenience, let \(P\) denote this path. Next, we present how \(n_{i}\) travels along \(P\). According to the definition of an edge \(E(I)\), \(P\) is collision-free for \(n_{i}\). Furthermore, the length of every line segment of \(P\) is shorter than \(r^{cs}\). As \(n_{i}\) encounters an agent in \(P\), \(n_{i}\) can move towards the next agent in \(P\) utilizing its local sensors. As \(n_{i}\) encounters an agent in \(P\), say \(n_{i}\), \(n_{i}\) accesses the next agent in \(P\) utilizing its local sensors. This is viable due to Assumption (A1). Note that global positioning is not required for this local maneuver. As \(n_{i}\) encounters the last agent in \(P\), \(n_{i}\) can move to its target point \(tgt_{n_{i}}\). This maneuver is performed using the local sensors of \(n_{i}\), based on Assumption (A2). After \(n_{i}\) encounters its target point \(tgt_{n_{i}}\), \(n_{i}\) initiates its local sensors. When \(n_{i}\) initiates its local sensors, several frontier points inside \(S(n_{i})\) are removed. Next, we verify that this removal is viable. Consider a case where a frontier point in \(F(n_{j})\) is inside \(S(n_{i})\). Because the relative distance between \(n_{j}\) and a frontier point in \(F(n_{j})\) is \(r^{cs}\), \(n_{j}\) is a neighbor to \(n_{i}\). Under Assumption (A1), \(n_{i}\) measures the relative position of \(n_{j}\). The relative vector from \(n_{i}\) to a frontier point in \(F(n_{j})\) is obtained by adding the following two vectors:  
1. The vector from \(n_{i}\) to \(n_{j}\)
2. The vector from \(n_{j}\) to the frontier point in \(F(n_{j})\)  
The above two vectors are accessible based on Assumptions (A1) and (A2). As \(n_{i}\) initiates its local sensors, several frontier points inside \(S(n_{i})\) are removed. Thereafter, \(n_{i+1}\) is deployed, finds a frontier point, and travels along \(T\) until meeting the frontier point. This continues until Algorithm 2 ends. Algorithm 2 is complete if \(i==N\) or if no frontier point is found using \(T\). In Algorithm 2, an agent \(n_{i}\) travels along a path in \(T\) until meeting \(tgt_{n_{i}}\). Consequently, we have the following Theorem 1. Theorem 1: _Every agent maneuvers utilizing Algorithm 2. When an agent \(n_{i}\) travels along a path in \(T\) until meeting \(tgt_{n_{i}}^{\prime}\), collision avoidance is assured. As \(n_{i}\) travels along a path in \(T\), say \(P\), \(n_{i}\) moves based on local interaction with sense-communication range \(r^{cs}\)._Proof. : Agent \(n_{i}\) travels along a path in \(T\), say \(P\), until meeting \(tgt_{n_{i}}\). Let \(P=\{m_{1}\to m_{2}\to\cdots\to m_{end}\}\) define the agents along the path. After \(n_{i}\) encounters \(m_{j}\) (\(j\leq end-1\)), \(n_{i}\) moves to \(m_{j+1}\). Furthermore, after \(n_{i}\) encounters \(m_{end}\), \(n_{i}\) moves to \(tgt_{n_{i}}\). The maneuver of \(n_{i}\) is performed using the local sensing measurements of \(n_{i}\) under Assumptions (A1) and (A2). According to the definition of an edge \(E(I)\), \(P\) is collision-free for \(n_{i}\). Furthermore, the length of every line segment of \(P\) is shorter than its sense-communication range \(r^{cs}\). Thus, the theorem is proved. Consider an ideal case where \(Q=\infty\). We then have Theorem 2. Theorem 2 proves that when the 3D network is fully constructed utilizing Algorithm 2, then no coverage holes remain. When no coverage holes exist, every puck in the 3D cluttered workspace is detected.