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



Главная

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

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

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

English
 Home

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


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

Яndex



   Главная / Курсовые проекты / Робот, ищущий выход из лабиринта (версия для печати)


Робот, ищущий выход из лабиринта



(C) 2003 М.А. Подтопельный, А.А. Чеботарева, А.А. Шалыто

Санкт-Петербургский государственный институт точной механики и оптики (технический университет)

Отсюда можно скачать полный текст документации в формате pdf (210 кб)

Аннотация

С тех пор, как впервые появилась проблема поиска выхода из лабиринта, было предложено множество способов ее решения. Для алгоритмизации и программирования решения этой задачи, оказалось удобным применить SWITCH-технологию. Подробно ознакомиться с этой технологией и с конкретными примерами ее использования можно на сайтах http://is.ifmo.ru и http://www.softcraft.ru.

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

При реализации проекта была разработана среда, способная отображать клетчатое поле, на котором для формирования лабиринта могут быть расставлены стены.

Для прохода по лабиринту применяется робот, интеллект которого описывается графом переходов конечного автомата. Действия робота протоколируются.

При использовании среды могут быть построены лабиринты, отвечающие следующим требованиям:

  • лабиринт плоский (не имеет третьего измерения);
  • все его коридоры параллельны или перпендикулярны друг другу;
  • лабиринт не меняется во время его прохода роботом.

Толщина стен и коридоров лабиринта считается одинаковой, так как это не влияет на решение задачи. Кроме того, лабиринт содержит перекрестки, в каждом из которых "встречаются" как минимум два коридора разных направлений.

Входные данные для среды задаются xml-файлом, в котором указаны:

  • размеры лабиринта;
  • координаты точки входа в лабиринт S;
  • координаты точки выхода из лабиринта F;
  • конфигурация лабиринта (список пар координат, задающих стены лабиринта).

Для реализации проекта были выбраны технология Flash и язык Action Script, как наиболее перспективные и удобные инструменты для визуализации проектов, работающих в сети Internet. Использование этих средств, а также автоматного подхода, позволило обеспечить удобство разработки и наглядность проекта, а также резко сократить трудоемкость написания программы.


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