Игровой алгоритм поможет саперам

Роботами-саперами сегодня никого не удивишь – их давно и успешно используют по всему миру, однако деятельность каждого из них осуществляется под чутким руководством удаленного оператора. Новая разработка сотрудников американского университета Duke потенциально способна заставить роботов действовать самостоятельно.

Общие черты

«Однажды вечером мы сидели на кухне и играли в CLUE, -- рассказывает доцент инженерной школы при университете Duke Сильвия Феррари корреспонденту университетского интернет-портала. – Неожиданно я поняла, что в этой игре невозможно посетить все комнаты с уликами, а наоборот, чем меньше ходов делаешь и больше улик собираешь, тем ближе подходишь к цели. Когда робот ищет мину, он сталкивается с такой же ситуацией: чтобы не взорваться, он должен делать как можно меньше движений, но должен собрать максимальное количество информации о местности, в которой он работает, и в итоге найти бомбу».

Вечерняя игра оказалась отправной точкой трехлетнего исследования, итогом которого стал математический алгоритм, описывающий, прежде всего, беспроигрышную стратегию в CLUE (подробнее о правилах игры – в нашем видеосюжете), но отлично применимую и в робототехнике. Алгоритм описывает процесс выбора, с которым игроки постоянно сталкиваются в CLUE, а также процесс сбора информации, необходимой для победы в игре.

После создания разработку протестировали в схватках с опытными игроками в CLUE и другими алгоритмами искусственного интеллекта. И в случаях, когда противниками алгоритма были люди, и когда ими оказывались другие алгоритмы, новая разработка достигала цели на 68--72 процента быстрее, чем ее соперники.

Один из популярнейших сетевых проектов, основанных на идеях искусственного интеллекта -- игра «20 вопросов», в которой компьютер, задавая пользователю ряд шутливых тематических вопросов, выясняет и сообщает ему, кем он является на самом деле. Как правило система выдает имена знаменитых людей от кинематографа и музыкальной сцены. Ну, а если кроме шуток, то поговорить с подлинным искусственным интеллектом в сети все же можно. На сайте проекта A.L.I.C.E. живет очаровательная роботесса по имени Элис, которая на вопрос «Do you speak russian?» отвечает: «Spasibo. Nyet» и вообще умеет поддержать несложную беседу. Правда, пока только на английском языке.

«Результаты испытаний говорят об абсолютном успехе нашего алгоритма, --

говорит Феррари. – Он (алгоритм) строго придерживался своей стратегии: за счет умения интегрировать новую информацию в уже имеющуюся он смог принять максимальное количество правильных решений, сделать минимум движений по карте и выиграть так быстро, как это вообще возможно».

Охота за сокровищами

«Ключ к успеху как в игре CLUE, так и в работах по разминированию местности с помощью автономного робота заключается не столько в сборе новой информации, сколько в умении использовать эту новую информацию для того, чтобы следующий шаг был правильным, -- объясняет партнер Сильвии Феррари по исследовательской деятельности Ченгуй Цай. – Этот обучающе-адаптивный процесс продолжается до тех пор, пока игрок, наконец, не выиграет, а робот – не обезвредит обнаруженную мину».

Исследователи искусственного интеллекта называют подобные ситуации проблемой «охоты за сокровищами». Сравнение предельно верное, поскольку и роботы-саперы, и игроки в CLUE, и пираты из авантюрных романов находятся в примерно одинаковых условиях: имеется карта местности, на которой спрятаны подсказки, ведущие к зарытому в землю сундуку. Даром, что у робота вместо сундука – бомба.

Проблему «охоты за сокровищами» уже давно пытаются решить с помощью различных методов математического моделирования, а игры – настольные и компьютерные – очень часто используются в качестве наглядной иллюстрации работы этих методов.

«CLUE, по нашему мнению, идеально подходит для иллюстрации работы нового алгоритма, -- продолжает Цай. – На примере этой игры замечательно виден его потенциал. Этот алгоритм показывает внушительное превосходство как над живыми игроками, так и над другими компьютерными программами».

Впрочем, все основные испытания – полевые, с использованием автономных роботов – еще впереди. Именно они и покажут, умеет ли новый алгоритм искать настоящие боеприпасы так же хорошо, как ищет игровых злодеев.