Главная arrow книги arrow Копия Глава 11. Основы планирования arrow Анализ различных подходов к планированию
Анализ различных подходов к планированию

Иногда возможность эффективного решения задачи обеспечивается путем определения того, какие отрицательные взаимодействия могут быть исключены. Задача называется имеющей упорядочиваемые подцели, если существует такой порядок подцелей, что планировщик может достичь их в указанном порядке, не будучи вынужденным отменять какую-либо из ранее достигнутых подцелей. Например, если в мире блоков цель состоит в построении столбика (например, в котором блок А стоит на В, который, в свою очередь, стоит на С, стоящем, в свою очередь, на столе, Table), то подцели являются упорядочиваемыми снизу вверх: если вначале будет достигнута подцель "С на Table", то никогда не придется ее отменять в ходе достижения других подцелей. Планировщик, в котором используется такой прием с упорядочением снизу вверх, способен решить любую задачу в проблемной области мира блоков без возвратов (хотя и может оказаться, что он не всегда находит самый короткий план).

В качестве более сложного примера укажем, что для планировщика Remote Agent, который управлял космическим аппаратом Deep Space One агентства NASA, было определено, что высказывания, касающиеся управления космическим аппаратом, являются упорядочиваемыми. По-видимому, в этом нет ничего удивительного, поскольку космический аппарат проектируется его разработчиками так, чтобы была возможность управлять им как можно проще (разумеется, с учетом всех прочих ограничений). Пользуясь преимуществом последовательного упорядочения целей, планировщик Remote Agent был способен в процессе планирования устранять основную часть поиска. Это означает, что он оказался достаточно быстродействующим для того, чтобы с его помощью можно было управлять этим космическим аппаратом в реальном времени, а такая задача раньше казалась невыполнимой.