Max Home IndustryВ одной из самых запоминающихся сцен из блокбастера 2002 года «Отчет меньшинства» Том Круз вынужден скрываться от роя паукообразных роботов, обыскивающих высокий жилой комплекс. В то время как большинство зрителей, вероятно, заинтригованы маленькими, подвижными заменами ищейки, компьютерный инженер может вместо этого восхищаться их элегантной системой управления.
В многоэтажном здании с множеством комнат, сотнями препятствий и тысячами мест для осмотра несколько десятков роботов движутся как единое целое. Они рассредоточены по схеме поиска, чтобы тщательно проверить все здание, одновременно разделяя задачи, чтобы не тратить время на повторение собственных путей или повторную проверку мест, которые уже посетили другие роботы.
Такой сплоченности было бы сложно достичь диспетчерам-людям, не говоря уже о том, чтобы искусственный контроллер мог выполнять вычисления в реальном времени.
«Если проблема управления связана с тремя или четырьмя роботами, которые живут в мире с несколькими комнатами, и если совместная задача определяется простыми логическими правилами, есть современные инструменты, которые могут вычислять оптимальное решение, которое удовлетворит задачу в разумные сроки «, — сказали Майкл М. Завланос, Мэри Милус Йох и Гарольд Л. Йох, младший доцент кафедры машиностроения и материаловедения в Университете Дьюка.
«И если вас не волнует наилучшее возможное решение, вы можете решить еще несколько комнат и более сложные задачи за считанные минуты, но все равно только дюжину вершин роботов», — сказал Завланос. «Более того, существующие алгоритмы не в состоянии преодолеть огромное количество возможностей в поиске решения».
В новой статье, опубликованной 29 апреля в Интернете в Международном журнале исследований робототехники , Завланос и его недавний аспирант Яннис Кантарос, который в настоящее время является докторантом Пенсильванского университета, предложить новый подход к этой проблеме, называемый STyLuS *, для крупномасштабного оптимального синтеза временной логики, который может решать задачи, значительно превышающие то, что могут обрабатывать существующие алгоритмы, с сотнями роботов, десятками тысяч комнат и очень сложными задачами, в одном небольшая часть времени.
Чтобы понять основы нового подхода, нужно сначала понять линейную темпоральную логику, что вовсе не так страшно, как кажется. Предположим, вы хотите запрограммировать несколько роботов, которые будут собирать почту из района и доставлять ее в почтовое отделение каждый день. Линейная темпоральная логика — это способ записать команды, необходимые для выполнения этой задачи.
Например, эти команды могут включать посещение каждого дома в последовательном порядке, возвращение в почтовое отделение и затем ожидание, пока кто-нибудь заберет собранную почту, прежде чем снова отправиться в путь. Хотя это может быть легко сказать по-английски, сложнее выразить математически. Линейная темпоральная логика может сделать это, используя свои собственные символы, которые, хотя для обычного наблюдателя могут показаться клингонскими, они чрезвычайно полезны для выражения сложных проблем управления.
«Термин линейный используется, потому что моменты времени имеют уникального преемника, основанного на дискретной линейной модели времени, а термин« временной »относится к использованию таких операторов, как« до »,« далее »,« в конце концов »и« всегда », — сказал Кантарос. «Используя этот математический формализм, мы можем создавать сложные команды, такие как« посетить все дома, кроме дома два »,« посетить дома три и четыре в последовательном порядке »и« подождать, пока вы не побываете в доме один, прежде чем идти в дом пять . ‘ «
Чтобы найти контроллеры роботов, которые удовлетворяют таким сложным задачам, местоположение каждого робота отображается в дискретной точке данных, называемой «узлом». Затем из каждого узла существует несколько других узлов, которые могут стать следующим потенциальным шагом для робота.
Традиционный контроллер просматривает каждый из этих узлов и возможные пути между ними, прежде чем найти лучший способ пройти через них. Но по мере того, как количество роботов и локаций для посещения увеличивается, а логические правила становятся все более сложными, пространство решений становится невероятно большим за очень короткое время.
Простая задача с пятью роботами, живущими в мире с десятью домами, может содержать миллионы узлов, фиксируя все возможные местоположения роботов и их поведение для выполнения задачи. Для этого требуется много памяти для хранения и вычислительная мощность для поиска.
Чтобы обойти эту проблему, исследователи предлагают новый метод, который вместо того, чтобы строить эти невероятно большие графики целиком, вместо этого создает меньшие аппроксимации с древовидной структурой. На каждом этапе процесса алгоритм случайным образом выбирает один узел из большого графа, добавляет его в дерево и перенаправляет существующие пути между узлами в дереве, чтобы найти больше прямых путей от начала до конца.
«Это означает, что по мере развития алгоритма это дерево, которое мы постепенно увеличиваем, становится все ближе и ближе к реальному графу, который мы никогда не строим», — сказал Кантарос. «Поскольку наш инкрементный граф намного меньше, его легко хранить в памяти. Более того, поскольку этот граф является деревом, поиск по графу, который в противном случае имеет экспоненциальную сложность, становится очень простым, потому что теперь нам нужно только отслеживать последовательность родительских узлов. вернуться к корню, чтобы найти желаемый путь. «
Долгое время считалось, что растущие деревья нельзя использовать для поиска возможных решений подобных проблем управления роботами. Но в статье Завланос и Кантарос показывают, что они могут заставить его работать, применяя два умных трюка. Во-первых, алгоритм выбирает следующий узел для добавления на основе информации о текущей задаче, что позволяет дереву быстро приблизить хорошее решение проблемы. Во-вторых, даже несмотря на то, что алгоритм выращивает деревья, он все же может обнаруживать циклы в исходном пространстве графа, которые фиксируют решения таких задач временной логики.
Исследователи показывают, что этот метод всегда найдет ответ, если он есть, и в конечном итоге всегда найдет лучший из возможных. Они также показывают, что этот метод может дать ответ экспоненциально быстро. При работе с проблемой 10 роботов, выполняющих поиск в сетке размером 50 на 50 — 250 домов, которые могут забрать почту — современные современные алгоритмы находят оптимальное решение за 30 минут.
STyLuS * делает это примерно за 20 секунд.
«Мы даже решили проблемы с 200 роботами, которые живут в сетке размером 100 на 100, что слишком велико для современных алгоритмов», — сказал Завланос. «Хотя в настоящее время нет систем, которые использовали бы 200 роботов для чего-то вроде доставки пакетов, они могут появиться в будущем. И им потребуется структура управления, такая как STyLuS *, чтобы иметь возможность доставлять их, удовлетворяя сложные логические правила. . «