Scheduling safe movement of air traffic in crowded air spaces

David W. Hildum; Stephen F. Smith; David W. Hildum; Stephen F. Smith

doi:10.1017/S0269888912000239

Abstract: This paper considers the problem of generating conflict-free movement schedules for a set of vehicles that are operating simultaneously in a common airspace. In both civilian air traffic management and military air campaign planning contexts, it is crucial that the movements of different vehicles be coordinated so as to avoid collisions and near misses. Our approach starts from a view of airspace management as a 4D resource allocation problem, where the space in which vehicles must maneuver is itself managed as a capacitated resource. We introduce a linear octree representation of airspace capacity to index vector-based vehicle routes and efficiently detect regions of potential conflict. Generalizing the notion of contention-based search heuristics, we next define a scheduling algorithm that proceeds by first solving a relaxed version of the problem to construct a spatial capacity profile (represented as an octree), and then using spatio-temporal regions where demand exceeds capacity to make conflict-avoiding vehicle routing and scheduling decisions. We illustrate the utility of this basic representation and search algorithm in two ways. First, to demonstrate the overall viability of the approach, we present experimental results using data representing a realistically sized air campaign planning domain. Second, we define a more abstract notion of ‘encounter set’, which tolerates some amount of conflict on the assumption that on-board deconfliction processes can take appropriate avoidance maneuvers at execution time, and show that generation of this more abstract form of predictive guidance can be obtained without loss in computational efficiency.

Other Articles By Authors

Scheduling safe movement of air traffic in crowded air spaces

The Robotics Institute

Corresponding authors: David W. Hildum ; Stephen F. Smith

Published online: 26 July 2012

Abstract: Abstract: This paper considers the problem of generating conflict-free movement schedules for a set of vehicles that are operating simultaneously in a common airspace. In both civilian air traffic management and military air campaign planning contexts, it is crucial that the movements of different vehicles be coordinated so as to avoid collisions and near misses. Our approach starts from a view of airspace management as a 4D resource allocation problem, where the space in which vehicles must maneuver is itself managed as a capacitated resource. We introduce a linear octree representation of airspace capacity to index vector-based vehicle routes and efficiently detect regions of potential conflict. Generalizing the notion of contention-based search heuristics, we next define a scheduling algorithm that proceeds by first solving a relaxed version of the problem to construct a spatial capacity profile (represented as an octree), and then using spatio-temporal regions where demand exceeds capacity to make conflict-avoiding vehicle routing and scheduling decisions. We illustrate the utility of this basic representation and search algorithm in two ways. First, to demonstrate the overall viability of the approach, we present experimental results using data representing a realistically sized air campaign planning domain. Second, we define a more abstract notion of ‘encounter set’, which tolerates some amount of conflict on the assumption that on-board deconfliction processes can take appropriate avoidance maneuvers at execution time, and show that generation of this more abstract form of predictive guidance can be obtained without loss in computational efficiency.

HTML

Acknowledgments

The work reported in this paper has been supported in part by the Boeing Company under contract CMU-BA-GTA-1-BOEING and the CMU Robotics Institute. The authors would like to thank Paul C. Parks and Patrick D. Hoy of the Boeing Company for sharing their expertise and providing valuable feedback and ideas about this work. Additionally, the authors are grateful to the reviewers for their insightful comments and suggestions with respect to earlier versions of this paper.

Note that no attempt is currently made to enforce any of the real-world constraints that govern the maneuverability of a vehicle being routed in this manner. Refinement of these large-grained route vectors could be performed later as an iterative post-processing step. Alternatively, the route modifier itself could be enhanced to generate more detailed and feasible alterations.

Note, as previously, that this method generates rather simple air routes: the expectation is that a more sophisticated route planner will eventually be employed for this process.

The total central processing unit time required by the current version of the system to generate both this octree and the priming run octree from Figure 5 is 40.4 s (Franz Allegro Common Lisp v8.1 on a 2.8 GHz Intel Core 2 Duo Apple iMac).

Referring back to Figure 8, the five bases shown across the top of the figure were removed.

Rights and permissions

References (21)

About this article

Cite this article

David W. Hildum, Stephen F. Smith. 2012. Scheduling safe movement of air traffic in crowded air spaces. The Knowledge Engineering Review 27(3)309−331, doi: 10.1017/S0269888912000239

David W. Hildum, Stephen F. Smith. 2012. Scheduling safe movement of air traffic in crowded air spaces. The Knowledge Engineering Review 27(3)309−331, doi: 10.1017/S0269888912000239

{{lists.name}}

Scheduling safe movement of air traffic in crowded air spaces

Abstract

Rights and permissions

References

About this article

Cite this article

Article Metrics

Access History

Other Articles By Authors