# Three-Dimensional Multi-Agent Foraging Strategy Based on Local Interaction
## 5 3D Multi-Agent Foraging Strategy
### Collection of All Pucks
#### 5.2.1 All Agents Except for the Guiding Agents Rendezvous at the Base  
When the 3D workspace has been entirely sensed utilizing Algorithm 2, every puck is sensed by at least one agent. Under Algorithm 2, every puck in the 3D workspace is detected by an agent in \(AgentsWithPucks\). A path can now be generated from the base to every agent in \(AgentsWithPucks\). Every agent on the path to an agent in \(AgentsWithPucks\) is utilized as a waypoint for guiding agents in moving between the base and the pucks. Let \(path(n_{1},n)\in T\) define a path from \(n_{1}\) to \(n\). Every agent on \(path(n_{1},n_{p})\) for all \(n_{p}\in AgentsWithPucks\) is called a _guiding agent_. Every agent except for the guiding agents is called a _carrier agent_, and has the task of carrying a puck to the base. We first make all agents except for guiding agents rendezvous at the base, as they now need to work as carrier agents. Algorithm 4 is used to make all agents except for guiding agents rendezvous at the base. Algorithm 4 was inspired by the distributed rendezvous control presented in [43]. The distinction between our article and [43] is that here we need to make all agents except for guiding agents rendezvous at the base. The guiding agents need to stay at their position in order to guide the carrier agents in moving between the base and the pucks. Algorithm 4 presents the gathering algorithm used to make all agents except for the guiding agents rendezvous at the base. ```
1: Let \(n_{1}\) denote an agent located at the base;
2: Apply Algorithm 1 in Section 5.1.1 for generating a tree \(T\) rooted at \(n_{1}\);
3:repeat
4:\(n\leftarrow\) every agent, other than guiding agents;
5:if\(n\) is a leaf in \(T\)then
6: The agent \(n\) moves along a path to \(n_{1}\) using \(ancestor(n)\) (\(n\) keeps visiting its ancestors using \(T\));
7:elseif\(n\) is not a leaf in \(T\)then
8:if\(n\) encounters all its descendants except for guiding agents then
9: The agent \(n\) moves along a path to \(n_{1}\) using \(ancestor(n)\) (\(n\) keeps visiting its ancestors using \(T\));
10:endif
11:endif
12:until every agent, other than guiding agents, visits \(n_{1}\);
```  
**Algorithm 4** Distributed gathering strategy for all agents except for guiding agents  
Assume that an agent, say \(n\), is not a guiding agent. Suppose that \(n\) has a guiding agent, say \(n_{g}\), as its ancestor in \(T\). In this case, \(n\) can visit agents along the path to the base, which contains \(n_{g}\). This implies that \(n\) utilizes \(n_{g}\) as a \"waypoint\" along the path to the base. Under Algorithm 4, an agent waits until it has met all its descendants except for guiding agents. Because \(n_{g}\) is a guiding agent, \(n_{g}\) must not move at all under Algorithm 4. Thus, \(p(n_{g})\) removes \(n_{g}\) from its descendants list; \(p(n_{g})\) starts moving after all of its descendants other than \(n_{g}\) have met \(p(n_{g})\). In this way, all agents except for guiding agentsrendezvous at the base. When these agents have gathered at the base, they are used as carrier agents for carrying the pucks to the base. To implement Algorithm 4, each agent stores its parent in \(T\), its descendant list, and its guiding agents. The following theorem shows that Algorithm 4 is distributed and that every agent is connected to \(n_{1}\) while it moves. Moreover, collision avoidance is assured while every agent is moving. Theorem 4.1: _Algorithm 4 is distributed, and every agent is connected to the root \(n_{1}\) while it moves. Moreover, collision avoidance is assured while every agent is moving._  
Proof: Suppose that an agent \(n\) has been visiting agents along the path to the root \(n_{1}\) in Algorithm 4. For convenience, let \(PATH\) indicate this path. Suppose that \(PATH\) consists of a set of agents \(p_{1}\to p_{2}\to p_{3}\cdots\to p_{end}\) in this order. Here, \(p_{end}\) is \(n_{1}\). According to the definition of an edge \(E(I)\), \(PATH\) is collision-free for \(n\).