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