Моделирование процесса поиска пути в лабиринте при помощи UML диаграмм и сетей Петри

Марков Александр Владимирович

аспирант по специальности 05.13.01 “Системный анализ, управление и обработка информации (в промышленности)”, НГТУ, г. Новосибирск

E-mail: muviton3@mail.ru

Романников Дмитрий Олегович

аспирант по специальности 05.13.01 “Системный анализ, управление и обработка информации (в промышленности)”, НГТУ, г. Новосибирск

E-mail: dmitry.romannikov@gmail.com

Воевода Александр Александрович

д. т. н., профессор кафедры автоматики, НГТУ, г. Новосибирск

E-mail:

I. Введение

Разработка программного обеспечения включает выделение свойств системы на основе анализа модели предметной области и требований к ПО.

В зависимости от класса создаваемого ПО используют «ручное» проектирование, либо пользуются различными средствами его автоматизации. Описывая характеристики ПО, применяют разнообразные нотации – блок-схемы, ER-диаграммы, UML-диаграммы, DFD-диаграммы, а также сети Петри.

Применение UML диаграмм совместно с сетями Петри [2, 4] предоставляет разработчикам возможность выявить неточности еще при постановки задачи. Анализ динамики функционирования системы можно описать через свободный язык сетей Петри [1].

Сети Петри — математический аппарат для исследования систем. Считается, что анализ сетей содержит важную информацию о структуре и динамическом поведении моделируемой системы.

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

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

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

II. Описание системы

Разрабатываемая система представляет собой лабиринт размерностью 5х5, включающий в себя проходы, стены, клетку входа и клетку выхода. Метка будет начинать движение с клетки “начало” и заканчивать в клетке “конец”.

Лабиринт (рис. 1) задан двухмерным массивом x[i][j]. Элементы массива будет равняться 1 или 0 (0 – проход, 1 – стена).

Реализация системы происходит с помощью UML диаграмм, основанных на алгоритмах из работ  [5 - 8].

Вначале, проектируется диаграмма классов (рис. 2), состоящую только из одного класса “робот”, который обращается к массиву лабиринт.

Нужно выделить, что при движение “робота” по лабиринту, в нем будет накапливаться история перемещений. Опираясь на методы разработки программного обеспечения [6 - 8], реализуем структурную диаграмму (рис. 3), состоящую из начального состояния (InitialState) и составного состояния – moving. На рисунке 4 представлено вложенные состояние, описывающее движение “робота”.

Применение комментариев [9] в состояниях, позволяет указать на нюансы, которые должны быть реализованы в сети Петри. В проектируемой системе это сохранение истории передвижений в фишке.

III. Реализация с помощью сетей Петри

Построение цветной сети Петри (рис. 5) происходит по правилам преобразований UML-сети Петри [6 - 8].

Примечание saveHistory: true, изображенное на рисунке 4, указывает на сохранении истории в метке. Чтобы реализовать сохранение истории была добавлена переменная “h” к местам с типом данных IIDS. При срабатывании одного из переходов Cond1, Cond2, Cond3 and Cond4 к фишке добавляется история перемещений.

Примечания в UML диаграммах могут применяться для построения UML диаграмм, ориентированных на время.

Место Final может содержать только фишки, которые нашли выход из лабиринта. История передвижений, заложенная в фишке, позволяет отследить маршрут, по которому двигался “робот” до клетки “конец”.

IV. Анализ сети Петри

Сеть Петри (рис. 5) была построена в программной среде CPN Tools, которая может быть использована для анализа систем. В ходе анализа системы был сформирован отчёт, представленный в таблице 1.

Таблица 1. Отчет о пространстве состояний для системы (рис. 5).

В сети присутствуют «мертвые» маркировки, что означает наличие в модели тупиковых состояний. Тупиковые состояния возникают, когда роботы не могут найти выход из лабиринта.

V. Выводы

Представлен механизм преобразования UML диаграмм в сети Петри. Данную методику можно применять для более общего представления UML диаграммам и временных сетей Петри.

Ещё одним важным результатом является сохранение в метке истории её передвижений. История перемещений может дать информацию о движении метки по лабиринту до клетки “конец”, что может быть использовано для анализа систем.

Так как задание массива в программном пакете CPN Tools трудоёмко, можно предложить использование внешних программ, например Excel.

Список литературы

1.            Воевода А.А. Марков А.В. О компактном представлении языков сетей Петри: сети с условиями и временные сети: сб. науч. тр. НГТУ. Новосибирск: Изд-во Новосиб. ун-та, 2010, № 2. С. 77 – 83.

2.            Воевода А.А. Марков А.В. Тестировании UML-диаграмм с помщью аппарата сетей Петри на примере разработки ПО для игры «Змейка: сб. науч. тр. НГТУ. Новосибирск: Изд-во Новосиб. ун-та, 2010, №3. С. 51 – 61.

3.            Воевода А.А. Романников Д.О. Использование UML и временных сетей Петри при разработке программного обеспечения: сб. науч. тр. НГТУ. Новосибирск: Изд-во Новосиб. ун-та, 2010, № 3. С. 61 – 71.

4.            Зимаев И.В. О возможности автоматической трансляции UML диаграмм деятельности в сети Петри: сб. науч. тр. НГТУ. Новосибирск: Изд-во Новосиб. ун-та, 2010, № 1. С. 149 – 156.

5.            Воевода А.А. Романников Д.О. Зимаев И.В. Применение UML-диаграмм и сетей Петри при разработке встраиваемого программного обеспечения: научный вестник НГТУ. Новосибирск: Изд-во Новосиб. ун-та, 2009, №4. С. 169 – 175.

6.            Коротиков С.В. Применение сетей Петри в разработке программного обеспечения центров дистанционного контроля и управления: дис. канд. техн. Наук / НГТУ. Новосибирск: Изд-во Новосиб. ун-та, 2008.

7.            L. Baresi, M. Pezze, On formalizing UML with high-level Petri net, Concurrent object-oriented programming and Petri nets: advances in Petri nets. Berlin: Heidelberg. Springer, 2003. P. 276 – 304.

8.            J. Campos, J. Merseguer, On the integration of UML and Petri nets in software development, Lecture Notes in Computer Science. Berlin: Heidelberg. Springer, 2006. P. 19 – 36.

9.            S. Bernardi, J. Merseguer Performance evaluation of UML design with Stochastic Well-formed Nets: The Journal of Systems and Software. 2007. -80 р.