Consider unmanned airborne vehicle (UAV) control agents in a dynamic multi-agent system. The agents must have a set of goals such as destination airport and intermediate positions. At the same time, the agents have to avoid gun shootings which move to their neighbors randomly. Agents try to build and execute plans that yield a high probability of successfully achieving the targets. The plans are developed based on the negotiations between different UAVs in the region with the overall goal in mind. The information about enemy defenses can be communicated between UAVs and they can negotiate about the paths to be taken based on their resources, such as fuel, load, available time to complete the task and the information about the threat. By constructing a Markov Decision Process (MDP) in this paper, we derive the optimal path. Combining the MDP and the sample path technique, we obtain the maximum probability that the UAVs successfully reach the target.