ITMO University
“Programming Technologies” Department



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Геном
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



    / Projects / The robot, searching an exit from the maze (версия для печати)


The robot, searching an exit from the maze



(C) 2003 M.A. Podtopelny, A.A. Chebotareva, A.A. Shalyto

Saint-Petersburg State Institute of Fine Mechanics and Optics (Technical University)

From here it is possible to download the full text of documentation in Russian in a PDF-format (210 Kb)

Annotation

Many ways of solving the problem of searching an exit from the maze were suggested since it's appearance. Very convenient technology for solving and algorithmizing this problem is SWITCH- technology. You can find more detailed description of this technology and samples at http://is.ifmo.ru and http://www.softcraft.ru.

The purpose of this article is to realize the "left-hand" maze beat algorithm. The idea of this algorithm is to walk holding the left hand on the left wall. This means that every cross you must choose the most left corridor.

The environment able to display the checked field on which may be set some walls forming the maze was developed to realize the project.

The robot whose intellect is described by the finite automata transition graph is used to beat the maze. Robot's actions are recorded.

The limitations for the mazes able to be used are:

  • the maze must be two-dimensional;
  • all it's corridors must be either parallel or perpendicular to each other;
  • the maze mustn't evaluate.

The walls' width and corridors' width are assumed to be a constant through this assumption doesn't influence the problem's solution. Besides the maze contains crosses where at the minimum two corridors of two different directions "meets".

The input data is given in xml-file which contains:

  • maze size;
  • entrance (point S) coordinates;
  • exit (point F) coordinates;
  • maze configuration (the list of coordinate pairs which define the maze walls).

The Flash-technology and Action Script language were chosen to realize the project through they are the most perspective and convenient instruments for visualizing Internet-related applications. Using them and automata method made the developing process easy and the project obvious.


© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com