В последние годы появились алгоритмы планирования, учитывающие факторы неопределенности, — изменчивость времени поездки, нестабильность каналов связи, неточности в показаниях датчиков и т. п. Исследователи из МТИ и Австралийского национального университета решили еще более сложную задачу, разработав алгоритм планирования, который автоматически создает резервные планы на случай провала основного, а также определяет условия, при которых нужно переключиться на «план Б», — например, это могут быть определенные показания датчиков или величина задержки. Алгоритм дает математические гарантии того, что риск провала генерируемых им планов будет ниже порога, заданного пользователем.
Пространство возможных решений в новом планировщике представлено в виде графа, путь по которому выбирается в зависимости от соотношения возможных преимуществ и потерь. Учет вероятностей сильно усложняет задачу создания резервных планов: скажем, поездка на автобусе в среднем занимает 15 мин, но есть определенная вероятность, что она может быть 35 мин и т. п. Решение — перед созданием графа попросить пользователя установить пороги риска. К примеру, исследователю, проектирующему систему сбора данных для дорогостоящего подводного робота, будет достаточно вероятности 90% того, что тот проведет все нужные замеры, но необходима вероятность 99,9% того, что робот не разобьется о скалу. Эти пороги становятся для алгоритма «бюджетом риска», который расходуется по мере прохождения графа различными маршрутами. Если какая-то ветвь слишком дорого обходится, ее отбрасывают. Чтобы процесс оценки проходил быстро, используются простые правила эвристики. Скажем, прохождение некой ветви в любом случае требует поездки на автомобиле между двумя точками — разными маршрутами, но если проезд по прямой на максимальной скорости чреват неприемлемыми задержками, вся ветвь отбрасывается.
По словам ученых, если эвристика будет оптимистичной — возможно, недооценивающей риски, но никогда не переоценивающей их, — ветви можно отбрасывать без снижения качества результирующих планов. В своей работе исследователи описывают способ создания линейных апроксимаций сложных распределений вероятности, с которыми намного проще работать математически. За счет этого компьютер оценивает их в тысячи раз быстрее, чем нелинейные распределения, что позволяет генерировать резервные планы «на ходу», по мере появления новой информации.
Алгоритм высоко оценили в НАСА, отметив, что решена очень важная задача для миссий космического агентства, в которых все шире используются автономные системы.
