БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Слово робот получило широкую известность после выхода в 1921 году пьесы R.U.R. (Rossum's Universal Robots — универсальные роботы Россума) чешского драматурга Карела Чапека. В этой пьесе роботы, которые выращивались из химических растворов, а не конструировались механически, в конечном итоге взбунтовались против своих создателей и решили взять над ними верх. Считается [562], что это слово фактически придумал брат Карела Чапека, Йозеф, который скомбинировал чешские слова "robota" (принудительный труд) и "robotnik" (раб), получив слово "robot", которое он применил в своем рассказе Opilec, изданном в 1917 году.
Термин "робототехника" (robotics) был впервые использован Айзеком Азимовым [46]. Но само понятие робототехники (которое было известно под многими другими названиями) имеет гораздо более долгую историю. В древнегреческой мифологии упоминается механический человек по имени Талое, который был спроектирован и построен греческим богом огня и кузнечного дела Гефестом. В XVIII столетии разрабатывались восхитительные автоматы (одним из первых примеров таких автоматов является механическая утка Жака Вокансона, созданная в 1738 году), но сложное поведение, которое они демонстрировали, было полностью задано заранее. Возможно, одним из примеров программируемого устройства, подобного роботу, был ткацкий станок Жаккарда (1805 год), описанный в главе 1.
Первым коммерчески поставляемым роботом был робот-манипулятор, получивший название Unimate (сокращение от universal automation — универсальная автоматизация). Робот Unimate был разработан Джозефом Энджелбергером и Джорджем Деволом. В 1961 году первый робот Unimate был продан компании General Motors, в которой он использовался при изготовлении телевизионных трубок. Тот же 1961 год примечателен и тем, что в этом году Девол получил первый патент США на конструкцию робота. Через одиннадцать лет, в 1972 году, корпорация Nissan впервые автоматизировала весь сборочный конвейер с помощью роботов, разработанных компанией Kawasaki на основе роботов, поставляемых компанией Unimation Энджелбергера и Девола. Эта разработка стала началом важной научно-технической революции, которая вначале происходила в основном в Японии и США и до сих пор продолжается во всем мире. Следующий шаг был сделан компанией Unimation в 1978 году, когда ее сотрудниками был разработан робот PUMA (сокращение от Programmable Universal Machine for Assembly — программируемая универсальная машина для сборки). Робот PUMA, первоначально разработанный для компании General Motors, стал фактически стандартом робототехнических манипуляторов на два следующих десятилетия. В настоящее время количество действующих роботов во всем мире оценивается в один миллион, причем больше половины из них установлено в Японии.
Литературу по робототехническим исследованиям можно разделить приблизительно на две части: мобильные роботы и стационарные манипуляторы. Первым автономным мобильным роботом можно считать "черепаху" Грея Уолтера, которая была создана в 1948 году, хотя ее система управления не была программируемой.
Робот "Зверь Хопкинса" (Hopkins Beast), созданный в начале 1960-х годов в Университете Джона Хопкинса, был гораздо более сложным; он имел аппаратные средства распознавания образов и был способен обнаружить крышку стандартной розетки питания переменным током. Этот робот обладал способностью находить розетки, подключаться к ним и перезаряжать свои аккумуляторы! Тем не менее "Зверь" имел ограниченный набор навыков. Первым мобильным роботом общего назначения был "Shakey", разработанный в конце 1990-х годов в институте, называвшемся тогда Станфордским научно-исследовательским институтом (Stanford Research Institute; теперь он носит название SRI) [466], [1143]. "Shakey" был первым роботом, в котором объединялись функции восприятия, планирования и выполнения, и это замечательное достижение оказало влияние на многие дальнейшие исследования по искусственному интеллекту. К другим важным проектам относятся Stanford Cart и CMU Rover [1082]. В [303] описано классическое исследование по автономным транспортным средствам.
В основе развития области робототехнической картографии лежат два различных источника. Первое направление начиналось с работы Смита и Чизмена [1440], которые применяли фильтры Калмана для одновременного решения задач локализации и составления карты. Разработанный ими алгоритм был впервые реализован в исследовании, описанном в [1095], а в дальнейшем дополнен в [912]. В [400] описано современное состояние дел в этой области. Второе направление началось с разработки представления в виде сетки занятости для вероятностной картографии, в которой задается вероятность того, что каждый участок (х,у) занят некоторым препятствием [1083]. Обзор современного состояния дел в робототехнической картографии можно найти в [1508]. Одной из первых работ, в которой было предложено использовать топологическую, а не метрическую картографию, стимулом для которой послужили модели пространственного познания человека, была [863].
Обзор самых ранних методов локализации мобильных роботов приведен в [153]. В теории управления фильтры Калмана применяются в качестве метода локализации в течение многих десятилетий, а в литературе по искусственному интеллекту общая вероятностная формулировка задачи локализации появилась гораздо позже, благодаря работам Тома Дина и его коллег [356], [362], а также Симонса и Кёнига [1412]. В последней работе был предложен термин марковская локализация. Первым практическим приложением этого метода явилась работа Бургарда и др. [208], которые создали целый ряд роботов, предназначенных для использования в музеях. Метод локализации Монте-Карло, основанный на фильтрах частиц, был разработан Фоксом и др. [488] и в настоящее время получил широкое распространение. В фильтре частиц, действующем по принципу Рао-Блэквелла, объединяются средства фильтрации частиц для локализации робота со средствами точной фильтрации для составления карты [1074], [1106].
В течение последнего десятилетия общим стимулом для проведения исследований по мобильным роботам служат два важных соревнования. Ежегодное соревнование мобильных роботов общества AAAI впервые было проведено в 1992 году. Первым победителем соревнования стал робот Carmel [287]. Наблюдаемый прогресс остается стабильным и весьма впечатляющим: в одном из последних соревнований (2002 год) перед роботами стояла задача войти в комплекс зданий, где проводилась конференция, найти путь к бюро регистрации, зарегистрироваться на конференции и произнести речь. В соревновании Robocup, инициатором проведения которого в 1995 году стал Китано со своими коллегами [802], провозглашена цель — к 2050 году
"разработать команду полностью автономных роботов-гуманоидов, которые смогут победить команду чемпионов мира по футболу среди людей". Игры происходят в лигах для роботов, имитирующих людей, колесных роботов различных размеров и четырехногих роботов Aibo компании Sony. В 2002 году это соревнование привлекло команды почти из 30 различных стран и на нем присутствовало больше 100 тысяч зрителей.
Исследования по созданию роботов-манипуляторов, которые первоначально именовались машинами "рука—глаз", развиваются в нескольких весьма различных направлениях. Первой важной работой по созданию машины "рука—глаз" был проект Генриха Эрнста под названием МН-1, описанный в тезисах его докторской диссертации, которые были опубликованы в Массачусетсском технологическом институте [441]. Проект Machine Intelligence, разработанный в Эдинбурге, также стал одной из первых демонстраций впечатляющей сборочной системы, основанной на использовании средств машинного зрения, которая получила название Freddy [1044]. После того как был сделан этот решающий начальный вклад, основные усилия были сосредоточены на создании геометрических алгоритмов для решения задач планирования движения в детерминированной и полностью наблюдаемой среде. В оригинальной работе Рейфа [1274] было показано, что задача планирования движения робота является PSPACE-трудной. Представление на основе пространства конфигураций было предложено Лозано-Пересом [956]. Важное влияние оказал ряд статей Шварца и Шарира, посвященных задачам, которые были ими названы задачами для грузчиков-тяжеловесов (piano mover) [1371].
Метод рекурсивной декомпозиции ячеек для планирования в пространстве конфигураций был впервые предложен в [193] и существенно доработан в [1646]. Самые первые алгоритмы скелетирования были основаны на диаграммах Вороного [1313] и Аграфах видимости [1581]. В [603] приведены результаты разработки эффективных методов инкрементного вычисления диаграмм Вороного, а в [253] диаграммы Вороного были распространены на гораздо более широкий класс задач планирования движения. В тезисах докторской диссертации Джона Кэнни [219] предложен первый полностью экспоненциальный алгоритм планирования движения с использованием еще одного метода скелетирования, называемого алгоритмом силуэта. В книге Жан-Клода Латомба [891] рассматривается целый ряд подходов к решению задачи планирования движения. В [780] описаны методы разработки вероятностных дорожных карт, которые в настоящее время относятся к числу наиболее эффективных методов. Планирование тонких движений с ограниченными сенсорными данными исследовалось в [217] и [957] на основе идеи интервальной неопределенности, а не вероятностной неопределенности. В навигации на основе отметок [902] используются во многом такие же идеи, как и в других областях исследования мобильных роботов.
Управлению роботами как динамическими системами (для решения задач манипулирования или навигации) посвящен огромный объем литературы, поэтому в данной главе лишь кратко рассматриваются сведения, касающиеся этой области. К числу важнейших работ относятся трехтомник по импедансному управлению Хо-гана [668] и общее исследование по динамике роботов Физерстоуна [456]. Дин и Уэллман [363] были в числе первых, кто попытался связать воедино теорию управления и системы планирования на основе искусственного интеллекта. Тремя классическими учебниками по математическим основам робототехнического манипулирования являются [305], [1184] и [1634]. Важное значение в робототехнике имеет также область проблем схватывания, поскольку тема определения стабильных условий приложения захвата является весьма сложной [998]. Для того чтобы иметь возможность создать успешно действующее средство схватывания, необходимо обеспечить восприятие данных о прикосновении, или тактильную обратную связь, для определения усилия контакта и обнаружения проскальзывания [455].
Понятие управления на основе поля потенциалов, с помощью которого предпринимаются попытки одновременно решать задачи планирования движения и управления, было введено в сферу робототехники Хатибом [793]. В технологии мобильных роботов эта идея стала рассматриваться как практический способ решения задачи предотвращения столкновений, а в дальнейшем была дополнена и легла в основу алгоритма гистограмм векторного поля [154]. Функции навигации, представляющие собой робототехническую версию политики управления для детерминированных задач MDP, были предложены в [812].
Вокруг проблемы создания архитектур программного обеспечения для роботов ведутся оживленные дискуссии. Истоками трехуровневой архитектуры стали исследования, проводившиеся еще в эпоху так называемого "старого доброго искусственного интеллекта", в том числе исследования по созданию проекта Shakey; общий обзор на эту тему приведен в [525]. Обобщающая архитектура была предложена Родни Бруксом [189], хотя аналогичные идеи были разработаны независимо Брейтенбер-гом [172], в книге которого, Vehicles, описан ряд простых роботов, основанных на поведенческом подходе. Вслед за успешным созданием Бруксом шестиногого шагающего робота был разработан целый ряд других проектов. Коннелл описал в своих тезисах докторской диссертации [288] результаты разработки мобильного робота, способного находить объекты, проект которого был полностью реактивным. Описания попыток распространить поведенческий принцип на системы, состоящие из нескольких роботов, можно найти в [999] и [1176]. Результатом обобщения идей робототехники, основанной на параллельно организуемом поведении, стало создание универсальных языков управления роботами GRL [681] и Colbert [832]. В [38] приведен обзор состояния дел в этой области.
Для управления мобильными роботами, выполняющими задания по разведке местности и доставке материалов, использовались также ситуационные автоматы [760], [1308], описанные в главе 7. Проекты ситуационных автоматов тесно связаны с проектами, основанными на организации поведения, поскольку они состоят из конечных автоматов, отслеживающих различные аспекты состояния среды с использованием простых комбинаторных схем. Тем не менее в подходе, основанном на организации поведения, подчеркивается отсутствие явного представления, а ситуационные автоматы конструируются алгоритмически из декларативных моделей среды таким образом, что представительное содержание каждого регистра состояния является полностью определенным.
В настоящее время имеется несколько хороших современных учебников по мобильной робототехнике. Кроме учебников, указанных выше, можно назвать сборник Кортенкампа и др. [846], в котором приведен исчерпывающий обзор современных архитектур систем мобильных роботов. В недавно изданных учебниках [423] и [1107] рассматриваются более общие вопросы робототехники. Еще в одной недавно изданной книге по робототехническому манипулированию рассматриваются такие сложные темы, как согласующее движение [997]. Основной конференцией по робототехнике является IEEE International Conference on Robotics and Automation. В число робототехнических журналов входят IEEE Robotics and Automation, International Journal of Robotics Research и Robotics and Autonomous Systems.
25.1. При любом конечном размере выборки результаты применения алгоритма локализации Монте-Карло являются смещенными (т.е. ожидаемое значение данных о местонахождении, вычисленные с помощью алгоритма, отличаются от истинного ожидаемого значения), поскольку именно так действуют алгоритм фильтрации частиц. В данном упражнении предлагается оценить это смещение.
Для упрощения рассмотрим мир с четырьмя возможными местонахождениями робота: x={xlfx2,x3fx4}. Первоначально осуществим равномерную выборку N>1 образцов среди этих местонахождений. Как обычно, вполне приемлемо, если для любого из местонахождений X будет сформировано больше одной выборки. Допустим, что z — булева сенсорная переменная, характеризующаяся следующими условными вероятностями:
P(z|xi) = 0.8 P(-iz|xi) = 0.2 P(zjx2) = 0.4 P(-iz|x2) = 0.6 P(zjx3) = 0.1 P(-iz|x3) = 0.9 P(z|x4) = 0.1 P(-iz|x4) = 0.9
В алгоритме MCL эти вероятности используются для формирования весов частиц, которые в дальнейшем нормализуются и используются в процессе повторной выборки. Для упрощения предположим, что при повторной выборке вырабатывается только один новый образец, независимо от N. Этот образец может соответствовать любому из четырех местонахождений X. Таким образом, процесс выборки определяет распределение вероятностей по X.
а) Каково результирующее распределение вероятностей по X для этого нового
образца? Ответьте на этот вопрос отдельно для N= 1,..., 10 и для N=°°.
б) Разница между двумя распределениями вероятностей Р и Q может быть
измерена с помощью дивергенции кь, которая определяется следующим
образом:
Каковы значения дивергенции KL между распределениями в упр. 25.1, а и истинным распределением апостериорных вероятностей? в) Какая модификация формулировки задачи (а не алгоритма!) гарантировала бы, чтобы конкретное приведенное выше выражение для оценки оставалось несмещенным даже при конечных значений А7? Предложите по меньшей мере две такие модификации (но каждая из них должна соответствовать предложенному заданию).