{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T18:37:43Z","timestamp":1767638263964,"version":"3.48.0"},"reference-count":21,"publisher":"Maximum Academic Press","issue":"3","license":[{"start":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T00:00:00Z","timestamp":1343260800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Knowledge Engineering Review"],"published-print":{"date-parts":[[2012,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>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 \u2018encounter set\u2019, 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.<\/jats:p>","DOI":"10.1017\/s0269888912000239","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T05:43:52Z","timestamp":1343281432000},"page":"309-331","source":"Crossref","is-referenced-by-count":2,"title":["Scheduling safe movement of air traffic in crowded air spaces"],"prefix":"10.48130","volume":"27","author":[{"given":"David W.","family":"Hildum","sequence":"first","affiliation":[]},{"given":"Stephen F.","family":"Smith","sequence":"additional","affiliation":[]}],"member":"27968","published-online":{"date-parts":[[2012,7,26]]},"reference":[{"key":"S0269888912000239_ref20","unstructured":"Yaman F. , Nau D. , Subrahmanian V. S. 2005. Going far, logically. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, Edinburgh, Scotland."},{"key":"S0269888912000239_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4439-5"},{"key":"S0269888912000239_ref18","unstructured":"Sridhar B. , Sheth K. , Smith P. , Leber W. 2005. Migration of FACET from Simulation Environment to Dispatcher Decision Support System. In Proceedings of the 24th Digital Avionics Systems Conference (DASC 2005), Washington, DC."},{"volume-title":"Intelligent Scheduling","year":"1994","author":"Smith","key":"S0269888912000239_ref16"},{"volume-title":"Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS","year":"1990","author":"Samet","key":"S0269888912000239_ref14"},{"key":"S0269888912000239_ref8","unstructured":"Hildum D. W. , Smith S. F. 2007. Constructing conflict-free schedules in space and time. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-07), Providence, RI."},{"key":"S0269888912000239_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jairtraman.2007.05.001"},{"key":"S0269888912000239_ref2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013617802515"},{"key":"S0269888912000239_ref1","unstructured":"Beck J. 1999. Texture Measurements as a Basis for Heuristic Commitment Techniques in Constraint-Directed Scheduling. PhD thesis, Department of Computer Science, University of Toronto."},{"key":"S0269888912000239_ref10","unstructured":"Myers K. L. , Smith S. F. , Hildum D. W. , Jarvis P. A. , de Lacaze R. 2001. Integrating planning and scheduling through adaptation of resource intensity estimates. In Proceedings of the 6th European Conference on Planning, Toledo, Spain."},{"key":"S0269888912000239_ref15","unstructured":"Smith S. , Becker M. , Kramer L. 2004. Continuous management of airlift and tanker resources: a constraint-based approach. Mathematical and Computer Modeling\u2014Special Issue on Defense Transportation: Algorithms, Models and Applications for the 21st Century 39(6\u20138), 581\u2013598."},{"key":"S0269888912000239_ref4","doi-asserted-by":"publisher","DOI":"10.2514\/atcq.12.1.75"},{"key":"S0269888912000239_ref13","unstructured":"Sadeh N. 1991. Look-ahead Techniques for Micro-Opportunistic Job Shop Scheduling. PhD thesis, School of Computer Science, Carnegie Mellon University."},{"key":"S0269888912000239_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"S0269888912000239_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(82)90058-2"},{"key":"S0269888912000239_ref17","doi-asserted-by":"crossref","unstructured":"Sridhar B. , Chatterji G. B. , Grabbe S. , Sheth K. 2002. Integration of traffic flow management decisions. In Proceedings of the AIAA Guidance, Navigation and Control Conference, Washington DC.","DOI":"10.2514\/6.2002-5014"},{"key":"S0269888912000239_ref12","unstructured":"Parker A. , Yaman F. , Nau D. , Subrahmanian V. S. 2007. Probabilistic go theories. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, India."},{"key":"S0269888912000239_ref3","doi-asserted-by":"crossref","unstructured":"Coppenbarger R. A. , Lanier R. , Sweet D. , Dorsky S. 2004. Design and development of the en route descent advisor (EDA) for conflict-free arrival metering. In Proceedings of the AIAA Guidance, Navigation and Control Conference, Providence, RI.","DOI":"10.2514\/6.2004-4875"},{"volume-title":"A Priority-Based Pre-Emption Algorithm for Incremental Scheduling with Cumulative Resources","year":"2002","author":"Zhou","key":"S0269888912000239_ref21"},{"key":"S0269888912000239_ref11","unstructured":"OR Concepts Applied 2002. Versatile Integrated Planner and Router (VIPR). DTIC Technical report, ADB279522."},{"volume-title":"A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing","year":"1966","author":"Morton","key":"S0269888912000239_ref9"}],"container-title":["The Knowledge Engineering Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0269888912000239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T14:44:06Z","timestamp":1767624246000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0269888912000239\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7,26]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7,26]]}},"alternative-id":["S0269888912000239"],"URL":"https:\/\/doi.org\/10.1017\/s0269888912000239","relation":{},"ISSN":["0269-8889","1469-8005"],"issn-type":[{"type":"print","value":"0269-8889"},{"type":"electronic","value":"1469-8005"}],"subject":[],"published":{"date-parts":[[2012,7,26]]}}}