In this paper a new collision-free 4D trajectory planning algorithm for an unmanned aerial vehicle in a common airspace with other aerial vehicles and static obstacles is presented. The collisions are detected by using an algorithm based on a grid model. The planning of a safe trajectory is based on a genetic algorithm. A Monte-Carlo method is used to evaluate the best simulated trajectory considering different sources of uncertainty as the wind, the aerial vehicle model inaccuracies and the limitations of the sensor and control system on board the aerial vehicle. Simulations have been carried out to study the characteristics of the new method. The paper also presents the results of experiments carried out in the airfield of Utrera in Seville (Spain) in February 2011.