Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 10/2018(9))

Теперь перейдем к описанию одной из технологий планирования, предназначенной для работы с неопределенностью. На протяжении многих лет исследователи в области исследований операций и принятия решений моделировали последовательные решения, используя Марковские процессы принятия решений (MDP). В принципе, MDP - это пространство состояний, в котором переходы между состояниями являются вероятностными по своей природе. В частности, они оказались полезными в задачах навигации робота, где есть неопределенность в расположении робота и ориентации после перемещения [20]. Размер пространства состояний по-прежнему является значительным препятствием для более широкого применения MDP-методов. Справедливости ради следует отметить, что альтернативные подходы (расширения методов POCL, Graphplan и SAT) для планирования с учетом неопределенности также не слишком хорошо зарекомендовали себя на практике. Перечислим некоторые другие недостатки MDP-методов. Во-первых, MDP предполагает, что после выполнения действия с неопределенным результатом агент может наблюдать полученное состояние. Во-вторых, в представлении MDP нет явной модели времени. Действия моделируются так, как если бы они были дискретными, мгновенными и бесперебойными. Как уже упоминалось, наличие вещественных величин и ограничений может вызвать большие трудности при планировании. В общем случае вещественные ограничения на действия могут быть нелинейными или могут включать производные. Простейший подход к работе с такими величинами при планировании состоит в том, что их следует игнорировать до тех пор, пока значения вещественных переменных не будут точно известны. Этот пассивный подход использовался в нескольких системах планирования [21], но он довольно слабый, поскольку обнаруживает трудности в конце процесса планирования и не дает никаких указаний при фактическом выборе соответствующего действия. Было построено несколько планировщиков, которые проверяют согласованность наборов вещественных ограничений еще до того, как все переменные известны. Несколько планировщиков использовали методы линейного программирования (LP) для управления этими ограничениями [4, 15]. Также известен планировщик LPSAT [15]. LPSAT использует методы LP совместно с методами планирования SAT. Задача планирования кодируется как проблема SAT, за исключением того, что вещественнозначные предусловия и результаты заменяются булевыми триггерными переменными в кодировке SAT. В ходе планирования, если триггерная переменная становится истинной, соответствующее ограничение передается инкрементному Simplex-решателю. Если Simplex-решатель сообщает, что набор ограничений несовместим, SAT отступает чтобы изменить одну или несколько триггерных переменных. Производительность LPSAT весьма перспективна, но метод имеет те же недостатки, что и основной SAT-подход. Другим подходом к обработке вещественнозначных величин является представление задачи планирования как смешанной целочисленной линейной задачи (ILP). В работах [22] обсуждаются методы перевода задач планирования в проблемы ILP. До сих пор методы ILP еще не конкурировали с методами планирования SAT, поскольку этап релаксации LP гораздо более дорогостоящий. Основным преимуществом подхода ILP является то, что все аксиомы, включая вещественные ограничения, переводятся в равенства и неравенства. 28