УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Построение автономного виртуального робота на основе автоматного подхода (на примере игры «CodeRally», предложенной на Java Challenge туре чемпионата мира по программированию по версии ACM 2003 г.)

(С) 2003 г. Е. М. Южаков
Научный руководитель: А. А. Шалыто, докт.техн.наук, профессор

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Отсюда можно скачать полный текст работы в формате pdf (700 кб)
Исходный текст программы (14 кб)

Аннотация

На командном чемпионате мира по программированию по версии ACM (Association for Computing Machinery) в качестве тренировочного тура участникам традиционно предлагается разработать программу управления роботом в некоторой виртуальной среде. При этом ежегодно изменяется как сам робот, так и «среда его обитания». Язык Java является единственным допустимым языком написания программы. После написания программы, созданные роботы соревнуются друг с другом. Поэтому тур называется Java Challenge.

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

При этом решаемой задачей является написание наиболее совершенной системы управления роботом (создание его искусственного интеллекта). Робот является виртуальным и автономным. Под автономностью понимается, что в процессе соревнований роботом управляет только его искусственный интеллект (после начала соревнований автор робота не имеет возможности воздействовать на него).

Для алгоритмизации и программирования верхнего уровня программы управления роботом представляется целесообразным использовать подход, основанный на SWITCH-технологии. Эта технология базируется на применении конечных автоматов и может быть эффективно использована для решения данной задачи, так как в ней естественным образом выделяются состояния объекта управления (робота).

Данная работа содержит анализ задачи CodeRally (Java Challenge 2003) [1] и одного из ее решений. Его особенностями, в отличие от предложенного нашей командой (SPb IFMO) на чемпионате мира, являются использование автоматного подхода и учет внутренних свойств среды обитания робота (виртуального мира).

Эффективность работы предложенного робота продемонстрирована в ходе соревнований с роботами, входящими в комплект поставки эмулятора, и с роботом, созданным нами на чемпионате мира. При этом разработанная программа набирает до 350 очков – величины близкой к теоретическому пределу.

Работа выполнена в рамках «Движения за открытую проектную документацию» [2]. Она является одним из решений проблемы, сформулированной на форуме сайта задачи CodeRally [1], состоящей в отсутствии достаточно сложных примеров ее решения, а тем более в отсутствии проектной документации на эти решения.

Для запуска робота необходимо иметь платформу Eclipse и эмулятор игрового мира. Процесс их установки подробно описан в соответствующей документации.

Источники

1. http://alphaworks.ibm.com/tech/coderally - сайт задачи CodeRally.
2. Шалыто А. А. Новая инициатива в программировании. Движение за открытую проектную документацию //Мир ПК. 2003. №10.