# 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  
In order to find every puck in the 3D bounded workspace, we propose a distributed puck search protocol (Algorithm 2). Algorithm 2 expands the agent network coverage while maintaining the network connectivity until no coverage holes remain in the workspace. For no coverage holes to remain, it must be the case that every puck has been sensed by at least one agent. In Algorithm 2, all agents are initially at the base. Then, every agent moves one after the other such that whenever each agent turns on its local sensors at its designated position (the target point in Algorithm 2) the unsensed open space is reduces gradually. In Algorithm 2, all agents are initially at the base. Therefore, every agent is a neighbor to \(n_{1}\). In the initial phase of Algorithm 2, \(n_{1}\) initiates its local sensors with range \(r^{cs}\) while staying at the base. Accordingly, frontier points of \(n_{1}\) are formed using the approach in Section 4. ```
\(N\) agents are located at the base, thus every agent is a neighbor to \(n_{1}\); \(\mathit{AgentsWithPucks}=\{\}\);  The agent \(n_{1}\) is at the base's entrance;  The agent \(n_{1}\) initiates its local sensors with range \(r^{cs}\), and frontier points of \(n_{1}\) are formed; \(i=2\); repeat  By running Algorithm 1 in Section 5.1.1, begin generation of \(T\) rooted at \(n_{i}\);  Algorithm 1 runs until an agent, say \(n^{\prime}\), receives a hop distance message from its neighbor in \(\mathcal{N}(n^{\prime})\) and a frontier point exists at \(n^{\prime}\); if\(n_{i}\) cannot find an agent with a frontier point then  This puck search algorithm is finished; endif \(P=path(n_{1},n^{\prime})\) in Algorithm 3;  Since \(n_{i}\) is a neighbor to \(n_{1}\) initially, the path information \(P\) is transmitted to \(n_{i}\);  The agent \(n_{i}\) moves along the path to \(n^{\prime}\);  Once \(n_{i}\) reaches \(n^{\prime}\), one frontier point on \(n^{\prime}\), say \(\mathit{tgt}_{n_{i}}\), is set as target point of \(n_{i}\);  The agent \(n_{i}\) moves to \(\mathit{tgt}_{n_{i}}\); if the agent \(n_{i}\) reaches \(\mathit{tgt}_{n_{i}}\)then  The agent \(n_{i}\) initiates its local sensors with range \(r^{cs}\), and detects its neighbors;  Frontier points of \(n_{i}\) are formed using the approach in Section 4; if\(n_{i}\) detects a puck then  AgentsWithPucks\(\_append(n_{i})\); endif endif \(i=i+1\); until\(i==N\);
```  
**Algorithm 2** Distributed puck search protocol for all agents  
Algorithm 2 applies to all agents. In Algorithm 2, every agent initiates its maneuver in the following order: \(n_{2}\to n_{3}\cdot\cdot\cdot\cdot\to n_{N}\). Whenever a new agent, say \(n_{i}\), initiates movement, it continues moving until meeting its target point. After meeting the target point, \(n_{i}\) initiates its local sensors with range \(r^{cs}\). This sensor initialization constructs frontier points for \(n_{i}\), as addressed in Section 4. Whenever each agent reaches its target point, the unsensed open space is gradually reduced. This iterates until every agent is located at its designated target point. In Algorithm 2, \(AgentsWithPucks\) denotes the set of agents that have detected a puck. Whenever an agent initiates its local sensor, it may detect a puck. When an agent detects a puck, that agent is added to the agent set \(AgentsWithPucks\). For instance, if an agent \(n_{i}\) detects a puck, \(AgentsWithPucks.append(n_{i})\) is performed as presented in Algorithm 2. In Algorithm 2, \(T\) rooted at \(n_{i}\) is generated by running Algorithm 1 from Section 5.1.1. Algorithm 1 runs until an agent, say \(n^{\prime}\), receives a hop distance message from its neighbor, say \(m\in\mathcal{N}(n^{\prime})\), and \(n^{\prime}\) has a frontier point. In this case, \(n^{\prime}\) needs to let \(n_{i}\) access a path to \(n^{\prime}\). Algorithm 3 is used to make \(n_{i}\) access a path to \(n^{\prime}\). In this algorithm, the initial path \(P=\{n^{\prime}\}\) is generated from \(n^{\prime}\).