Алгоритмы планирования широко используются в области логистики и управления. Они могут помочь компьютерам планировать рейсы и автобусные маршруты, управлять движением автономных роботов и определить политику контроля энергосистем.
В последние годы алгоритмы планирования начали учитывать непредвиденные ситуации, как путешествия, неустойчивые связи между автономными роботами, несовершенными данными датчиков, и тому подобное. Это приводит к тому, что масштаб проблемы планирования будет расти в геометрической прогрессии, но исследователи обнаружили умные способы эффективного решения этой проблемы, - передает Robotics.ua.
Исследователи из Массачусетского технологического института и Австралийского национального университета (ANU) разрабатывают алгоритм планирования, который также генерирует планы на непредвиденные случаи, если первоначальный план окажется слишком рискованным. Он также определяет условия с показаний датчиков для конкретного плана.
Несмотря на дополнительный труд, введенный генерацией планов на случай непредвиденной ситуации, алгоритм по-прежнему обеспечивает математические гарантии, что риск от планов неудачи упадет ниже некоторого порога у множества пользователей.
«Проблема с планированием непредвиденных обстоятельств заключается в том, что существует так много вещей, которые могут пойти не так, если вы сгенерировали планы для всех возможных ситуаций», - говорит Брайан Уильямс, профессор аэронавтики и астронавтики, чья команда разработала новую систему, - «Так что вопрос заключается в том, сколько непредвиденных обстоятельств вы сможете сгенерировать»?
Педро Сантана, аспирант аэронавтики и астронавтики, является первым автором проекта, описывающего систему, которую он представил на ежегодном собрании Ассоциации по улучшению искусственного интеллекта в минувшие выходные. К нему присоединяется Sylvie Thiébaux, профессор информатики в Австралийском национальном университете и исследователь программы Национального информационного центра коммуникационных технологий Австралии (NICTA), который имеет партнерские отношения с MIT.
Вероятностные решения
Как объясняет Уильямс, диапазон возможных решений, которые могут быть представлены в виде структуры данных, называется график. Каждый граф состоит из узлов, которые обычно представлены в виде кругов и кривых в виде отрезков, соединяющих узлы. Сетевые диаграммы и блок-схемы являются известными примерами графа.
В системе планирования каждый узел графа представляет собой точку принятия решения, например, «Должен ли я сесть на автобус или метро?» Путь через граф может быть оценен в соответствии с оценками, которые он предлагает при прибытии до места назначения благополучно, и минусов, которые он налагает при минимальном опоздании. Оптимальным планом является тот, который максимизирует оценки.
Факторы вероятностей делают такой тип расчета гораздо более сложным: средняя поездка на автобусе длиться 15 минут, но есть некоторая вероятность, что это будет 35; средняя поездка на метро может длиться 18 минут, но не более, чем 24. В этом контексте, даже на относительно простой задачи планирования вычисление планов непредвиденных ситуаций может быть чрезмерно трудоемким процессом.
Чтобы решить эту проблему, исследователи MIT и ANU заимствовали технику от некоторых более ранних работ из группы Уильямса. Перед тем, как планировщик начинает строить график, он запрашивает у пользователя установить пороговые значения риска. Исследователь пытается разработать план по сбору данных для робота стоимостью нескольких миллионов долларов, который может быть выполнен с вероятностью 90 процентов, если робот будет принимать все показания с датчиков, но они хотели добиться 99,9 процентов вероятности того, что робот не столкнется со сбоем при высокой скорости.
Алгоритм исследователей рассматривает эти пороги как «бюджет риска», который исследует пути через граф.
Оптимистичные перспективы
Исследователи используют несколько простых правил большого пальца, или на компьютерном языке - эвристики - оценивания графов. Каждый путь через данную отрасль, например, может включать в себя другой маршрут автомобиля между двумя точками, каждая со своим собственным распределением вероятностей возможного времени поездки. Но если движение по прямой линии между точками при максимально разрешенной скорости будет по-прежнему нести недопустимые задержки, нет никакого смысла в оценке вероятности для каждого маршрута.
Пока эвристика оптимистична - возможны недооценки риска, но не переоценки. Планировщик может отсечь графы без ущерба для планирования. Иногда эти эвристики зависят от приложений, наподобие тех, что оценивают маршруты геометрически. Но иногда это не так.
Одна из причин, что вероятностные распределения добавят много сложности к расчетам планирования, является то, что они нелинейные: их графики берут формы, которые являются более сложными, чем простые линии. В работе ученые описывают способ получения линейных приближений вероятностных распределений, что значительно облегчает работу математически.
Эти распределения вполне оптимистичны: они никогда не переоценивают риск. Но компьютер может оценить их в тысячи раз быстрее, чем возможно с нелинейным распределением. Такие эвристические предложения надеются, что системе планирования исследователей удастся обновить планы на лету, в свете новой информации, а также генерировать чрезвычайные ситуации заранее.
«Авторы решали очень важную проблему, которая имеет самое непосредственное отношение к миссиям NASA, где мы все более зависимым от автономного поведения, запрограммированного в нашем космическом корабле», - говорит Мишель Ингам, из технической группы надзора за системной архитектурой и моделями поведения в Лаборатории реактивного движения NASA. «Их работа особенно актуальна для миссий на поверхности астероидов и комет, планетарных тел, как Марс, или не слишком далеких в будущем миссий ледяных спутников, как Европа и Энцелад. Наши автоматические аппараты изучения этих локаций будут оспорены для эффективного выполнения своих задач в присутствии значительной неопределенности и избегания препятствий и опасностей».
По информации robotics.ua, авторы предложили способ и возможность для планирования деятельности робота, которые оптимизируют оценки, связанные с реализацией программных целей, ограничиваясь «риском выполнения» миссии. Это означает, что будущие операторы выполнения миссий смогут определить, насколько консервативным или агрессивным они хотят видеть их космический аппарат при выборе соответствующего риска, и есть ли гарантия, что космический корабль не будет превышать этот уровень риска».
В последние годы алгоритмы планирования начали учитывать непредвиденные ситуации, как путешествия, неустойчивые связи между автономными роботами, несовершенными данными датчиков, и тому подобное. Это приводит к тому, что масштаб проблемы планирования будет расти в геометрической прогрессии, но исследователи обнаружили умные способы эффективного решения этой проблемы, - передает Robotics.ua.
Исследователи из Массачусетского технологического института и Австралийского национального университета (ANU) разрабатывают алгоритм планирования, который также генерирует планы на непредвиденные случаи, если первоначальный план окажется слишком рискованным. Он также определяет условия с показаний датчиков для конкретного плана.
Несмотря на дополнительный труд, введенный генерацией планов на случай непредвиденной ситуации, алгоритм по-прежнему обеспечивает математические гарантии, что риск от планов неудачи упадет ниже некоторого порога у множества пользователей.
«Проблема с планированием непредвиденных обстоятельств заключается в том, что существует так много вещей, которые могут пойти не так, если вы сгенерировали планы для всех возможных ситуаций», - говорит Брайан Уильямс, профессор аэронавтики и астронавтики, чья команда разработала новую систему, - «Так что вопрос заключается в том, сколько непредвиденных обстоятельств вы сможете сгенерировать»?
Педро Сантана, аспирант аэронавтики и астронавтики, является первым автором проекта, описывающего систему, которую он представил на ежегодном собрании Ассоциации по улучшению искусственного интеллекта в минувшие выходные. К нему присоединяется Sylvie Thiébaux, профессор информатики в Австралийском национальном университете и исследователь программы Национального информационного центра коммуникационных технологий Австралии (NICTA), который имеет партнерские отношения с MIT.
Вероятностные решения
Как объясняет Уильямс, диапазон возможных решений, которые могут быть представлены в виде структуры данных, называется график. Каждый граф состоит из узлов, которые обычно представлены в виде кругов и кривых в виде отрезков, соединяющих узлы. Сетевые диаграммы и блок-схемы являются известными примерами графа.
В системе планирования каждый узел графа представляет собой точку принятия решения, например, «Должен ли я сесть на автобус или метро?» Путь через граф может быть оценен в соответствии с оценками, которые он предлагает при прибытии до места назначения благополучно, и минусов, которые он налагает при минимальном опоздании. Оптимальным планом является тот, который максимизирует оценки.
Факторы вероятностей делают такой тип расчета гораздо более сложным: средняя поездка на автобусе длиться 15 минут, но есть некоторая вероятность, что это будет 35; средняя поездка на метро может длиться 18 минут, но не более, чем 24. В этом контексте, даже на относительно простой задачи планирования вычисление планов непредвиденных ситуаций может быть чрезмерно трудоемким процессом.
Чтобы решить эту проблему, исследователи MIT и ANU заимствовали технику от некоторых более ранних работ из группы Уильямса. Перед тем, как планировщик начинает строить график, он запрашивает у пользователя установить пороговые значения риска. Исследователь пытается разработать план по сбору данных для робота стоимостью нескольких миллионов долларов, который может быть выполнен с вероятностью 90 процентов, если робот будет принимать все показания с датчиков, но они хотели добиться 99,9 процентов вероятности того, что робот не столкнется со сбоем при высокой скорости.
Алгоритм исследователей рассматривает эти пороги как «бюджет риска», который исследует пути через граф.
Оптимистичные перспективы
Исследователи используют несколько простых правил большого пальца, или на компьютерном языке - эвристики - оценивания графов. Каждый путь через данную отрасль, например, может включать в себя другой маршрут автомобиля между двумя точками, каждая со своим собственным распределением вероятностей возможного времени поездки. Но если движение по прямой линии между точками при максимально разрешенной скорости будет по-прежнему нести недопустимые задержки, нет никакого смысла в оценке вероятности для каждого маршрута.
Пока эвристика оптимистична - возможны недооценки риска, но не переоценки. Планировщик может отсечь графы без ущерба для планирования. Иногда эти эвристики зависят от приложений, наподобие тех, что оценивают маршруты геометрически. Но иногда это не так.
Одна из причин, что вероятностные распределения добавят много сложности к расчетам планирования, является то, что они нелинейные: их графики берут формы, которые являются более сложными, чем простые линии. В работе ученые описывают способ получения линейных приближений вероятностных распределений, что значительно облегчает работу математически.
Эти распределения вполне оптимистичны: они никогда не переоценивают риск. Но компьютер может оценить их в тысячи раз быстрее, чем возможно с нелинейным распределением. Такие эвристические предложения надеются, что системе планирования исследователей удастся обновить планы на лету, в свете новой информации, а также генерировать чрезвычайные ситуации заранее.
«Авторы решали очень важную проблему, которая имеет самое непосредственное отношение к миссиям NASA, где мы все более зависимым от автономного поведения, запрограммированного в нашем космическом корабле», - говорит Мишель Ингам, из технической группы надзора за системной архитектурой и моделями поведения в Лаборатории реактивного движения NASA. «Их работа особенно актуальна для миссий на поверхности астероидов и комет, планетарных тел, как Марс, или не слишком далеких в будущем миссий ледяных спутников, как Европа и Энцелад. Наши автоматические аппараты изучения этих локаций будут оспорены для эффективного выполнения своих задач в присутствии значительной неопределенности и избегания препятствий и опасностей».
По информации robotics.ua, авторы предложили способ и возможность для планирования деятельности робота, которые оптимизируют оценки, связанные с реализацией программных целей, ограничиваясь «риском выполнения» миссии. Это означает, что будущие операторы выполнения миссий смогут определить, насколько консервативным или агрессивным они хотят видеть их космический аппарат при выборе соответствующего риска, и есть ли гарантия, что космический корабль не будет превышать этот уровень риска».
Комментариев нет:
Отправить комментарий