METHOD FOR PROVIDING A COLLISION FREE PATH IN A THREE-DIMENSIONAL SPACE

A method for providing a collision free safe path includes storing predetermined spatial graphs representing the set of points defining the collision free paths within that region and calculating the shortest path over the region. Each of the points in the graph have associated therewith predetermined constraints which, where compared to real world navigational limitations, determine if the path is navigable. A collision free path is generated by first examining the set of points defining the path and comparing them with the real world limitations. If all of the available paths are not collision free on the prestored spatial graph, a modified spatial graph, at a different altitude if necessary, is defined with collision free paths and then the shortest path between two points on this graph determined and output to a navigation system. In the event that the initial navigational limitations are altered during traversing of the shortest path, the same process will be repeated, i.e., a new spatial graph can be generated defining the collision free paths and the shortest path determined along this new shortest path from the point at which the navigational limitations changed.