Страница 2 из 7 Разработки в области составления расписаний для аэрокосмических проектов имеют долгую историю. Программа T-Sched [412] использовалась для составления расписаний, представляющих собой последовательности принципиально важных команд для спутника Uosat-II. Программы Optimum-AIV [1] и Plan-ERSl [509], основанные на программе О-Plan, применялись в Европейском космическом агентстве, соответственно, для сборки космических аппаратов и планирования наблюдений. Программа Spike [741] использовалась для планирования наблюдений с помощью космического телескопа Хаббл в NASA, а система Space Shuttle Ground Processing Scheduling System [355] осуществляла составление производственного расписания с охватом вплоть до 16 000 рабочих смен. Программа Remote Agent [1108] стала первой автономной программой планирования и составления расписаний, применяемой для управления космическим аппаратом, которая работала на борту космического аппарата Deep Space One в 1999 году. В [1527] приведен обзор литературы по применению средств составления производственных расписаний в области исследования операций; теоретические результаты приведены в [993]. Применяемые в программе Strips средства для изучения макроопераций ("микрооператоров", состоящих из последовательности примитивных этапов) могут рассматриваться как первый механизм иерархического планирования [465]. Иерархия использовалась также в системе Lawaly [1410]. В системе Abstrips [1336] была реализована идея иерархии абстракции, на основе которой было разрешено игнорировать предусловия действий низкого уровня при планировании на более высоких уровнях, чтобы можно было проще выявить общую структуру рабочего плана. В тезисах докторской диссертации Остина Тэйта [1494] и в работе Эрла Сакердоти [1338] были разработаны основные идеи планирования HTN в его современной форме. Многие практически применяемые планировщики, включая O-Plan и Sipe, представляют собой планировщики HTN. В [1628] обсуждаются свойства действий, благодаря которым планирование HTN становится эффективным. В [443], [444] представлен планировщик с полной иерархической декомпозицией, а также приведен ряд результатов анализа сложности для чистых планировщиков HTN. Другие авторы [25], [72], [766], [1635] предложили гибридный подход, принятый в данной главе, согласно которому декомпозиции просто представляют собой еще одну форму уточнения, которая может использоваться в планировании с частичным упорядочением.
|