# Three-Dimensional Multi-Agent Foraging Strategy Based on Local Interaction
## 1 Introduction  
This paper considers a multi-agent foraging problem in which multiple autonomous agents find resources (called pucks) in a bounded workspace and carry the found resources to a designated location called the base. Every agent has limited capabilities and lacks sophisticated hardware such as a Global Positioning System (GPS). Every agent executes simple decision procedures in a decentralized manner, and there is no leader. Foraging has real-world applications, e.g., in the distributed cleanup of hazardous toxins or the automated construction and repair of artificial structures; in both of these situations, agents must first locate and then transport objects of interest (toxins in the former, building blocks in the latter) in a decentralized manner [1; 2; 3]. Collection and transport tasks have various applications, such as mine-clearing, hazardous waste cleanup, and search and rescue. Our paper handles multi-agent foraging, which involves multiple agents collecting randomly distributed resources (pucks) and carrying them back to a single position (base). We address 3D multi-agent foraging based on local interaction, which does not rely on global localization of an agent. In other words, GPS is not utilized by the agents. In this problem, multiple agents begin moving from the base with the goal of gathering all of the pucks, which are randomly distributed in the workspace. In the proposed solution, each agent is controlled such that they carry the sensed pucks back to the base while moving based on local interaction with their neighbors. In this way, an agent's maneuvering does not depend on global localization. We assume that each agent has local sensing, local communication, and movement abilities. Each agent can detect a nearby puck using its local sensors, such as a camera. We consider a case in which the agents move in an unknown 3D workspace with many obstacles that are not known in advance. In this case, obstacles can block a communication link between agents and hinder the motion of each agent. Each agent lacks any global localization or global communication. If an agent moves too far away from any other agent, it cannot communicate with the others due to the limited sense-communication range. Hence, an agent must stay within sense-communication range of at least one other agent while exploring the unknown 3D cluttered workspace. Our study considers a bounded 3D workspace which contains many unknown obstacles. Our search strategy is provably complete in detecting all pucks in a 3D cluttered bounded workspace which is not known in advance. We prove that under the proposed search strategy all pucks in the unknown bounded workspace are found in finite time. To the best of our knowledge, no paper in the literature has handled the 3D multi-agent foraging problem in our article. Moreover, our article is novel in letting multiple agents perform foraging and puck carrying in a 3D unknown cluttered workspace while not depending on global localization of an agent. We only use local interaction with maximum sense-communication range. The proposed foraging strategy has the following two steps. The first step in the proposed foraging strategy is to detect every puck in the 3D cluttered unknown workspace in a provably complete manner. Initially, all agents are located at the base. The search process is performed by moving agents one by one to expand the sensor coverage, until no coverage holes remain in the 3D cluttered bounded workspace. The 3D cluttered workspace is considered completely covered when every puck has been sensed by at least one agent. The second step in foraging is to collect the pucks and return them to the base. In the collection step, global localization and global communication cannot be utilized. Because the agents cannot use global localization, each agent moves based only on local interactions within its limited sense-communication range. The novel contributions of this paper are summarized as follows:  
1.