Главная / Алгоритм, позволяющий системам планирования эффективно создавать запасные планы
17.02.2016 |
|
 Алгоритмы планирования широко используются в области логистики и управления. Они могут помочь в планировании рейсов и автобусных маршрутов, управлении автономными роботами, и определении политики управления для энергосистем, среди других вещей.
В последние годы алгоритмы планирования начали учитывать неопределенности - вариации времени поездки, неустойчивую связь между автономными роботами, незавершенные данные датчиков и тому подобное. Это приводит к масштабным проблемам планирования, растущим в геометрической прогрессии, но исследователи обнаружили умные способы их эффективного решения.
Исследователи из Массачусетского технологического института и Австралийского национального университета сделали проблему еще более сложной, разработав алгоритм планирования, который также генерирует планы на случай непредвиденных обстоятельств, если первоначальный план окажется слишком рискованным. Он также определяет условия, которые запускают переключатель для конкретного плана.
Несмотря на дополнительный труд, введенный при генерации планов на непредвиденный случай, алгоритм по-прежнему обеспечивает математические гарантии того, что риск в случае неудачи плана опустится ниже некоторого порога, который задается пользователем.
Как объясняют исследователи, диапазон возможных решений, с которыми сталкивается планировщик, может быть представлен в виде структуры данных, называемых графом. Граф состоит из узлов, которые обычно представлены в виде кругов, и ребер, которые представлены в виде отрезков, соединяющих узлы. Сетевые диаграммы и блок-схемы являются известными примерами графа.
В системе планирования, каждый узел графа представляет собой точку принятия решения, например, «Должен ли я сесть на автобус или метро?» Путь через граф может быть оценен в соответствии с наградами, которые он предлагает (если вы доберетесь вовремя) и штрафами, которые он накладывает (опоздание на пять минут). Оптимальным является план, который максимизирует награду.
Учет вероятностей делает подобный тип расчета вознаграждения гораздо более сложным: средняя поездка на автобусе может составить 15 минут, но есть некоторая вероятность, что он доберется до места назначения за 35 минут; средняя поездка на метро может составлять18 минут, но почти никогда не превышает более 24 минут. В данном контексте даже при относительно простой задаче создание планов на случай чрезвычайных ситуаций может быть чрезмерно трудоемким.
Чтобы сделать проблему легко решаемой, исследователи заимствовали технику от некоторых более ранних работ. Перед тем, как планировщик начинает строить график, он запрашивает от пользователя установку пороговых значений риска. Алгоритм исследователей рассматривает эти пороги как «бюджет риска», который он тратит при исследовании путей через граф. Если планировщик определяет, что данная ветвь графика будет превышать бюджет, то он отбрасывает ее.
Однако подобное определение должно быть быстрым. Поэтому исследователи используют несколько простых правил большого пальца (или по-другому, эвристики) - для оценки тех или иных ветвей. Каждый путь через данную отрасль, например, может включать в себя другой маршрут автомобиля между двумя точками, каждый из которых имеет свое собственное распределением вероятностей возможных времени поездки. Но если обход прямой линии между точками при максимальной разрешенной скорости по-прежнему приведет к недопустимым задержкам, то нет никакого смысла в оценке вероятности для каждого маршрута. Следовательно, ветвь может быть устранена.
Пока эвристика остается оптимистичной, планировщик может отсечь ветви без ущерба для качества конечного плана. Иногда подобная эвристика зависят от приложения, наподобие тому, которое оценивает маршруты геометрически. Но иногда это не так.
Например, одна из причин, по которой вероятностные распределения добавляют столько сложности к расчетам планирования, заключается в том, что они являются нелинейными: их графики принимают формы, которые являются более сложными, чем простые линии. Исследователи разработали способ получения линейных приближений вероятностных распределений, что значительно облегчает работу с математической точки зрения.
Эти приближения являются оптимистичными: они никогда не переоценивают риск. Но компьютер может оценить их в тысячу раз быстрее, чем при нелинейном распределении. Подобная эвристика возлагает надежду на то, что система планирования исследователей может обновить планы на лету, в свете новой информации, а также генерировать чрезвычайные планы заранее.
|
|
