SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


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

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

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

Описание проекта в формате pdf (~680 кб)
Исходный текст программы на java (~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.