автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Управляемая тестами система имитационного моделирования наземного движения воздушных судов

кандидата технических наук
Щетинин, Денис Вячеславович
город
Тверь
год
2008
специальность ВАК РФ
05.13.11
цена
450 рублей
Диссертация по информатике, вычислительной технике и управлению на тему «Управляемая тестами система имитационного моделирования наземного движения воздушных судов»

Автореферат диссертации по теме "Управляемая тестами система имитационного моделирования наземного движения воздушных судов"

На правах рукописи

Щетинин Денис Вячеславович

УПРАВЛЯЕМАЯ ТЕСТАМИ СИСТЕМА ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ НАЗЕМНОГО ДВИЖЕНИЯ ВОЗДУШНЫХ СУДОВ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Тверь 2008

003455819

Работа выполнена на кафедре информационных технологий факультета прикладной математики и кибернетики Тверского государственного университета.

Научный руководитель доктор технических наук,

профессор Местецкий Леонид Моисеевич

Официальные оппоненты: доктор технических наук,

профессор

Эрлих Александр Игоревич

кандидат физико-математических наук Майсурадзе Арчил Ивериевич

Ведущая организация Московский государственный технический

университет гражданской авиации

Защита состоится 200& г. в ч. на заседании диссер-

тационного совета Д002.017.02 при Вычислительном центре им. А. А. Дородницына Российской академии наук по адресу: 119333, г. Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан А? ноз^^-Я. 2008 г.

Учёный секретарь диссертационного совета, доктор физико-математических наук, профессор В. В. Рязанов

Общая характеристика работы

Предмет исследования

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

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

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

Актуальность темы

Необходимость повышения эффективности технологий разработки, развитие информационных технологий, их широкое распространение и рост конкуренции на рынке информационных услуг заставляют сегодняшних разработчиков моделей работать в весьма жестких условиях. По сравнению с аналогичными проектами 70-х, 80-х и даже 90-х годов на порядки сокращены людские, временные и материальные ресурсы, которые могут быть привлечены для создания системы. Эти обстоятельства в сочетании с увеличением сложности моделируемых систем и требований к качеству имитационных программных комплексов делают весьма актуальной проблему повышения эффективности процесса разработки имитационных программных комплексов.

Имитационное моделирование представляет собой метод исследования сложных систем. В результате процесс разработки имитационных моделей сопровождается постояннъш изменением требований (и к самой модели, и к программному комплексу, в состав которого она входит). Соответственно, процесс разработки имитационной программной системы должен строиться как процесс постепенного формирования и уточнения требований к создаваемому программному продукту, то есть итеративно. При этом полностью спланировать его на ранних стадиях работы практически невозможно. Следовательно, программная реализация будет постоянно подвергаться изменениям. Поэтому эффективная методология создания имитационных моделей должна обеспечивать постоянную стоимость внесения изменений в существующий программный код на протяжении всего времени разработки — то есть, обеспечивать гибкость.

Традиционно методы разработки сложных программных систем ориентированы главным образом на подробное предварительное планирование всех этапов создания системы и в этом смысле являются прогно-зируюи1,ими — пытаются предугадать все возможные проблемы, с которыми разработчики могут столкнуться в процессе разработки и учесть их в проекте будущей системы. Очень часто такая организация процесса разработки требует привлечения больших коллективов разработчиков и приводит к весьма большим временным и материальным затратам. Но самое главное — использование прогнозирующих методологий не обеспечивает возможности внесения существенных изменений в требования по ходу разработки, так как это повлечет за собой нарушение всего плана работ и необходимость возврата к начальным стадиям (анализ требований — планирование — проектирование).

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

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

Приходится констатировать, что на сегодняшний день наметилось существенное отставание имитационного моделирования от других областей информационных технологий и программирования, где проблема гибкости решается на методологическом уровне. Во второй половине 90-х гг. основные подходы к решению этих проблем были сформулированы и опубликованы в виде манифеста гибких технологий. Данное направление, а также предложенные подходы достаточно быстро были признаны актуальными и перспективными, начались масштабные исследования по этой теме. К настоящему времени сформировался уже целый ряд гибких методологий, которые нашли нашли свое применение на практике в конкретных областях: прикладные программные комплексы, базы данных, сетевые технологии, web-ссрвисы, разработка пользовательских интерфейсов и т.д.

В данной работе рассматривается технический аспект организации разработки, который можно понимать как перевод плохо формализованных и неструктурированных требований, предъявляемых к программному продукту, на формализованный компьютерный язык. Среди различных подходов и методов, призванных обеспечить гибкость программного кода в техническом аспекте, выделяется методология управляемой тестами разработки (Test-Driven Development), синтезирующая в себе такие методы как «проектирование в коде», «сначала тесты», «постоянная переработка кода». Данный подход, разработанный около 10 лет назад, уже достаточно хорошо зарекомендовал себя и широко применяется на практике. Однако, вопрос использования данной методологии в имитационном моделировании остается малоизученным.

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

Цель работы

Цель работы ■- повышение эффективности разработки систем имитационного моделирования за счет обеспечения гибкости их программной реализации.

Предлагаемый подход к решению

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

• более высокую частоту выпуска промежуточных версий

• высокую степень интерактивности взаимодействия клиент - разработчик

• снижение временных и материальных затрат при развитии модели «от простого к сложному» за счет более полного использования результатов (программного кода), полученных на предыдущих итерациях.

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

Предлагаемый подход основывается на использовании методологии . Test-Driven Development (управляемой тестами разработки), фокусирующейся на инженерно-технических аспектах разработки программного обеспечения. Данная методология предлагает управлять процессом разработки с помощью постоянно развивающейся системы спецификаций, записанных в виде автоматических программных тестов. За счет этого данный подход позволяет:

• перевести процесс отражения требований в программный код на более формализованный уровень;

• организовать итеративную разработку, обеспечивая контроль изменений на всех этапах от формализации требований до их воплощения в программном коде;

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

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

Но применение данной методологии в такой специфической области как имитационное моделирование сталкивается с целым рядом проблем. В данной работе рассматриваются эти проблемы и предлагаются пути

их разрешения, обобщенные в метод управляемого тестами имитационного моделирования.

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

Задачи исследования

В соответствии с выбранным подходом для достижения поставленной цели необходимо решить следующие задачи:

• Провести теоретическое обоснование использования гибких методологий в имитационном моделировании дискретных систем

• Разработать метод управляемого тестами имитационного моделирования

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

• Экспериментально показать практическую эффективность метода управляемого тестами имитационного моделирования на примере реального, полномасштабного имитационного программного комплекса.

Результаты, выносимые на защиту

На защиту выносятся следующие результаты исследования:

• Метод управляемого тестами имитационного моделирования

• Созданная с использованием данного метода имитационная модель наземного движения воздушных судов по летному полю аэропорта и программный комплекс для проведения имитационных экспериментов с ней

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

Научная новизна

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

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

Практическая значимость

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

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

Апробация

Представленные в работе результаты докладывались и обсуждались на 1-ой и Н-ой всероссийских конференциях «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках» (Санкт-Петербург, 23 - 24 октября 2003 г. и 19 - 21 октября 2005 г. соответственно), конференции «Интеллектуализация обрабокти информации» (Алушта, Украина, 14 - 19 июня 2004 г.), на семинарах в ВЦ РАН и ТвГУ.

Публикации

По теме диссертации опубликовано 7 работ, в том числе, 1 работа [5] в рецензируемом журнале, рекомендуемом ВАК, и 6 работ в других изданиях: [1, 2, 3, 4, 6, 7].

Внедрение результатов

Выносимые на защиту методы были реализованы, исследованы и использованы для решения прикладных задач в ходе работ по проектам реконструкции международных аэропортов «Шереметьево», «Домодедово».

Краткое содержание

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

В первой главе обосновывается необходимость разработки метода построения имитационных моделей и программных комплексов на основе итеративного процесса развития системы по принципу «от простого к сложному» В основу предлагаемого метода положены принципы и подходы гибких методологий и, в частности, методологии Test-Driven Development1.

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

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

1 Kent Berk Test-Dnven Development: By Example. Addison-Wesley, 2003

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

( Описать задачу

>

Создание теста

( Формализовать условие теста )

X____/ [работает]

( Создать тело теста ^ —'

^выполнить тест [ проваливается]

5

(5

>

Реализация теста

Выбрать способ решения

^Релизовать выбранное решение

9

[проваливаются5

^Выт

.¡олнить все тесты

работают 1

I

К

Рефакторинг

Выявить проблемный код [тре6увVсярефэ^торинр]

"'С

[ке выявлено]

>

Переработать код

Выполнить все тесты

Г проваливаются]

Рис. 1. Схема итерации в контексте управляемой тестами разработки

Такая организация процесса разработки имеет целый ряд достоинств, среди которых прежде всего следует отметить следующие: • Тесты, выступая в роли средства формализации результатов планирования, анализа и проектирования, и формируя спецификацию для

и

реализации в программном коде, тем самым позволяют управлять процессом разработки

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

• Тесты являются средством контроля качества программной системы, причем как с точки зрения «внешней» функциональности системы (интересующей конечного пользователя), так и с точки зрения ее внутреннего устройства и программной реализации (важной для разработчиков)

• Тесты являются весьма эффективным средством документирования, поскольку наборы тестов достаточно подробно и абсолютно адекватно описывают поведение системы на всех уровнях абстракции

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

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

Создавать направляющие разработку тесты предлагается в соответствии с характерным масштабом осреднения времени2 на различных уровнях абстракции модели. В первом приближении можно выделить два базовых подхода: на основе числовой оценки выходных параметров медленной модели (статистические тесты) и анализ поведения быстрых моделей в составе тестируемой системы (событийное тестирова-

2Ю. Н. Павловский. Имитационные модели и системы. М .ФАЗИС.ВЦ РАН, 2000

ние). Событийное тестирование может быть реализовано в различных временных масштабах: от детального анализа отдельных событий, происходящих в элементарных компонентах системы, до более обобщенной оценки функционирования более крупных подсистем на более длительных отрезках времени. Удобным инструментом здесь являются протоколы — коллекции данных, с нужной степенью детализации описывающих события в моделируемой системе. Тестирование на основе протоколов, таким образом, занимает промежуточное положение между базовыми подходами, давая возможность варьировать степень детализации при тестировании.

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

Таким образом, метод управляемого тестами имитационного моделирования состоит в конкретизации способов создания тестов в рамках общей методологии Test-Driven Development.

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

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

Сложность управления крупным аэропортом определяется целым рядом факторов: необходимостью комплексного учета огромного количества различных факторов, взаимосвязи которых необозримы и носят сложный нелинейный характер, наличием многочисленных неопределенностей, связанных с самой спецификой авиаперевозок: нарушениями графиков подготовки судов к полету, опозданиями в прилете судов, нештат-

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

Наиболее важными показателями эффективности работы АП являются показатели пропускной способности. Известно, что задача оценки пропускной способности относится к теории массового обслуживания. АП может рассматриваться как система (или сеть) массового обслуживания (СМО). Однако прямое применение методов теории массового обслуживания для получения достаточно точной и детальной аналитической модели в рассматриваемом контексте практически невозможно. Входной поток заявок данной системы определяется прибытием и отправлением ВС и является нестационарным, к тому же обладает последействием. Поскольку время обслуживания отдельных заявок (определяемых временем руления ВС) зависит от структуры рулежной сети и от текущей ситуации на летном поле, нужно учитывать эту информацию при определении состояния СМО, что приводит к большой размерности вектора состояния. Саму СМО приходится рассматривать как многоканальную. Процессы обработки заявок (передвижения ВС) не описываются марковскими цепями. Эти и другие проблемы не позволяют получить аналитическую модель, обеспечивающую получение необходимых для принятия управляющих решений оценок. Альтернативой является технология имитационного моделирования, которую можно рассматривать как синтез традиционных математических подходов и (относительно) новых информационных технологий. Использование компьютерных имитационных моделей позволяет сочетать точность, надежность и обоснованность математических моделей с возможностью обработки больших объемов информации на современных вычислительных устройствах, обеспечивающих возможность детального анализа сложных систем, визуализации результатов прогнозирования, проведение экспертных оценок различных вариантов управляющих и проектных решений и т.п.

В данном конкретном случае компьютерная имитация даст возможность с нужной степенью детализации промоделировать процессы,

учитывая при этом все параметры проектных решений и статистические данные потоков ВС, получить как точные количественные оценки, так и обеспечить проведение качественного экспертного анализа. Имитационная модель аэропорта представляет интерес только в составе программного комплекса, который обеспечивает решение всех задач, связанных с проведением имитационных экспериментов: подготовку исходных данных, численную обработку выходных данных модели и получение статистических результатов, визуализацию полученных результатов и динамики функционирования системы, обоснование полученных результатов.

Формулируются следующие основные требования к модели и поддерживающему ее использование программному комплексу:

• Работа АП должна моделироваться для различных вариантов расписаний авиаперевозок, как существующих (например, с целыо проверки адекватности модели), так и прогнозных, полученных в результате модификации существующих

• В программном комплексе должна быть реализована возможность описания вариантов проектных решений, а также существующих условий работы АП в виде специальных объектов — сценариев, — допускающих простые способы создания, манипуляции и использования для проведения имитационных экспериментов

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

• Для получения экспертных оценок программный комплекс должен предоставить графическое анимированное отображение процесса движения ВС по летному полю как в реальном, так и в ускоренном масштабах времени

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

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

ния ВС осуществляется на основе анализа показателей пропускной способности АП. Наиболее значимыми показателями, характеризующими процесс движения ВС на летном поле в течение суток (по характеристикам времени руления и задержки во времени руления), являются:

• суточная динамика прилета и вылета ВС;

• суточная динамика количества ВС, стоящих в очередях;

• распределение времени руления ВС в течение суток;

• максимальное количество ВС, которым одновременно пришлось ожидать во время руления, за сутки;

• среднее время простоя в очередях по всем ВС за сутки;

• среднее время руления по всем ВС за сутки.

Имея оценки этих показателей, можно произвести сравнительный анализ работы АП в различных условиях и при различных исходных данных. Основными показателями при этом являются (1) способность АП в принципе обслужить весь поток ВС, предусмотренный расписанием, и (2) выполнение нормативов по времени руления ВС при вылете.

Важным вопросом является выбор технологии моделирования. Он связан с рядом конструкторских решений, принимаемых на основе анализа предъявляемых к системе требований и существующих технологий имитационного моделирования. Так, функционирование АП удобно описывать в терминах отдельных событий, таких как «начало движения по рулежной дорожке», «изменение скорости», «взлет», «[¡осадка» и т.д. Причем по времени эти события распределены неравномерно. Соответственно, имитационную модель наземного движения ВС целесообразно строить как дискретную систему. Наилучшее соотношение качества и точности моделирования в этой ситуации дает метод изменяющегося шага по времени (до следующего события). Программно модель реализована на универсальном языке программирования (С-1- +) с использованием ориентированной на имитационные процессы библиотеки моделирования.

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

• создание простейшей модели АП как одноканальной системы массового обслуживания

• моделирование работы элементов рулежной сети

• моделирование принятой в АП организации движения

• моделирование движения с изменяющейся скоростью и соблюдение дистанции между ВС

Каждая итерация начинается с неформального словесного описания задачи. Далее рассматриваются:

1. Формализация задачи в виде автоматического программного теста.

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

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

3. Рефакторинг — изменения программной системы, направленные на улучшение ее внутренней структуры, но не изменяющее ее внешнее поведение.

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

• формализованную спецификацию решаемых на каждой итерации задач, выполняемую непосредственно в программном коде в виде автоматизированного теста

• управление процессом разработки, путем варьирования спецификациями в создаваемых тестах

• контроль внесения изменений в программный код, за счет использования созданных тестов в качестве индикаторов функционального состояния программной системы

• управление качеством программного кода, оцениваемого по трудоемкости создания теста для очередной задачи,

• создание подробной технической документации к разрабатываемой системе, роль которой в значительной степени выполняют тесты

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

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

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

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

В задаче моделирования АП сценарий включает в себя:

• погодные условия;

• параметры организации воздушного движения: курс взлета/посадки, режим использования взлетно-посадочных полос, конфигурацию рулежной сети;

• расписание полетов (авиапотоки).

Очевидно, проведение имитационных экспериментов с большим количеством сценариев является трудновыполнимой на практике задачей. Разработанный программный комплекс позволяет сформировать набор наиболее важных сценариев и провести по ним имитационные эксперименты. Так, при анализе вариантов реконструкции АП «Шереметьево», в частности, для оценки варианта постройки третьего терминала, рассматривались три группы сценариев — см. рис. 2

Далее в главе рассматривается архитектура всего программного комплекса (см. рис. 3) и устройство имитационной модели.

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

Рис. 2. Принятые классы сценариев

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

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

Рис. 3. Структура программного комплекса

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

Рулежная (маршрутная) сеть представляется в виде ориентированного размеченного графа Г = (У,Ь,р), где

V — множество вершин, соответствующих выбранным концевым точкам линейных отрезков рулежной сети АП Ь = {{и, у) : и, и € V} — множество дуг (ориентированных ребер),

описывающих отдельные участки рулежной сети р : Ь —» Г, Р — множество меток (параметров, ассоциированных с дугами графа и определяющих поведение ВС на соответствующем участке).

Граф Г назовем графом рулежной (маршрутной) сети АП. Отдельные участки рулежной сети представляются парами вида (1,р(1)) (I Е Ь), которые были названы локациями. В программной реализации с локациями связан ряд алгоритмов, обеспечивающих моделирование движения ВС по рулежной сети (механизм блокировок, определение скорости движения, выбор маршрута руления и т.д.), а также визуализацию самих локаций и движения по ним с помощью аппарата кривых Безье.

Параметры ВС в модели представляются следующими атрибутами: идентификатор; тип (тяжелое, среднее, легкое); тип рейса (прилет или

вылет); маршрут движения; текущая локация; расстояние, пройденное по текущей локации; скорость; интервал движения; признак выполнения посадочной или взлетной операции и связанные с этим параметры; посадочные характеристики ВС.

Описывается также модель работы диспетчерских служб: диспетчера воздушной зоны, диспетчера старта и посадки, диспетчера руления.

Поведение модели в динамике реализуется с помощью следующих имитационных процессов:

• Движение ВС по маршруту.

Данный имитационный процесс обеспечивает моделирование изменения положения самолетов на летном поле АП.

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

• Управление взлетами. Данный имитационный процесс обеспечивает выдачу разрешения на выполнение взлетной операции.

• Моделирование входного потока ВС. Этот имитационный процесс обеспечивает своевременное появление ВС в системе (с учетом случайных отклонений от времени, указанного в расписании).

Оценка адекватности разработанной имитационной модели в работе проводится на примере задачи анализа вариантов реконструкции АП «Шереметьево», в частности изучения и оценки возможности постройки нового терминала. Анализ проводился путем сравнения параметров функционирования АП в двух конфигурациях: существующей (два терминала) и перспективной (три терминала). В частности, были поставлены и решены следующие задачи:

1. Проведена сравнительная оценка работы АП в двух указанных конфигурациях при хороших погодных условиях и при авиа- и пассажиропотоках нынешней интенсивности.

2. Проведена сравнительная оценка работы АП в двух указанных конфигурациях при ухудшении погодных условий

3. Проведена сравнительная оценка работы АП в двух указанных конфигурациях при хороших погодных условиях и' при перспективных авиа- и пассажиропотоках.

4. Выполнена оценка адекватности моделирования на основе вычислительных экспериментов с существующими расписаниями полетов.

Количественные оценки на основе х2_кРитерия показывают, что распределения времени ожидания ВС при простых погодных условиях и базовом расписании в существующей конфигурации и в конфигурации с новым терминалом практически (с вероятностью более 0,99) совпадают. То есть, ввод в эксплуатацию третьего терминала не скажется на качестве работы АП в простых погодных условиях при условии сохранения нагрузки.

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

В заключении сформулированы основные результаты работы:

• Проведено теоретическое обоснование использования гибких методологий в имитационном моделировании дискретных систем

• Разработан метод управляемого тестами имитационного моделирования

• На примере разработки имитационного программного комплекса моделирования наземного движения воздушных судов экспериментально показана практическая эффективность данного метода

• В рамках разработки данного имитационного программного комплекса решены следующие задачи:

— Проведен анализ предметной области, выбраны и формализованы показатели качества работы аэропорта, обосновано применение гибких методологий разработки

- Разработана методика сбора и подготовки исходных данных для построения направляющих тестов

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

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

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

- Проведена верификация и установлена адекватность имитационной модели и получаемых с ее помощью прогнозных оценок решаемым задачам

Таким образом, эффективность метода обоснована как теоретически, так и опытно-экспериментальным путем.

Публикации автора по теме диссертации

[1] Имитационное моделирование аэропорта — инструмент обоснования решений / Д. Щетинин, Л. Местецкий, А. Исаев, А. Федоров // Аэропорт Партнер. — 2002. — № 5-6.

[2] Щетинин, Д. Библиотека имитационного моделирования систем с дискретными событиями С-Ь+БШ / Д. Щетинин // Сборник докладов 1-ой всероссийской конференция «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках» (ИММОД-2003). — Т. I. - СПб: ФГУП ЦНИИ технологии судостроения, 2003.

[3] Щетинин, Д. Управляемая тестами разработка в применении к имитационному моделированию / Д. Щетинин ,// Сложные системы: обработка информации, моделирование и оптимизация: Сборник научных трудов. — Тверь: Тверской Государственный Университет, 2005.

[4] Щетинин, Д. Управляемая тестами разработка имитационных моделей / Д. Щетинин // Сборник докладов Н-ой всероссийской конференция «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках» (ИММОД-2005). - Т. I. - СПб: ФГУП ЦНИИ технологии судостроения, 2005.

[5] Щетинин, Д. Управляемое тестами имитационное моделирование / Д. Щетинин // Программные продукты, и сист.емы. — 2007. - № 3.

[6] Щетинин, Д. Имитационная модель наземного движения воздушных судов в аэропорту / Д. Щетинин. JI. Местецкий // Сборник докладов 1-ой всероссийской конференция «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках» (ИММОД-2003). — Т. II. — СПб: ФГУП ЦНИИ технологии судостроения, 2003.

[7] Щетинин, Д. Прогнозирование пропускной способности аэропорта на основе имитационного моделирования / Д. Щетинин, JI. Местецкий, А. Федоров // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции. — Симферополь: Крымский научный центр HAH Украины, 2004.

Технический редактор A.B. Жильцов Подписано в печать 14.11.2008. Формат 60 х 84^. Усл. печ. л. 1,5. Тираж 100 экз. Заказ № 351. Тверской государственный университет Редакционно-издательское управление Адрес: Россия, 170100, г. Тверь, ул. Желябова, 33. Тел. РИУ: (4822) 35-60-63.

Оглавление автор диссертации — кандидата технических наук Щетинин, Денис Вячеславович

Список сокращений

Введение

Глава 1. Метод управляемого тестами имитационного моделирования

1.1 Гибкие методологии в имитационном моделировании

1.2 Методология управляемой тестами разработки.

1.2.1 Понятие теста.

1.2.2 Процесс управляемой тсстами разработки.

1.2.3 Анализ методологии.

1.3 Управляемая тестами разработка имитационных моделей

1.3.1 Проблемы применения методологии управляемой тестами разработки в имитационном моделировании

1.3.2 Способы создания тестов

1.4 Выводы.

Глава 2. Принципы разработки системы моделирования аэропорта на основе гибких методологий

2.1 Имитационное моделирование в задачах проектирования и управления аэропортом.

2.2 Основные требования к программному комплексу.

2.3 Выбор и формализация показателей качества процессов наземного движения ВС.

2.3.1 Анализ показателей пропускной способности аэропортов

2.3.2 Показатели пиковых периодов в оценке работы аэропорта

2.3.3 Выбор показателей качества движения ВС по летному полю.

2.4 Выбор технологии построения имитационной модели . 73 2.4.1 Дискретная модель с шагом по времени до следующего события.

2.4.2 Имитационные процессы.

2.4.3 Использование универсального языка программирования в сочетании со специализированной библиотекой моделирования.

2.5 Выводы.7G

Глава 3. Управляемая тестами разработка системы моделирования аэропорта

3.1 Основные задачи разработки системы моделирования аэропорта

3.2 Процесс разработки.

3.2.1 Простейшая модель работы аэропорта.

3.2.2 Разбиение рулежной сети на участки

3.2.3 Дисциплина движения на отдельных участках рулежной сети: перекрестки.

3.2.4 Моделирование движения с изменяющейся скоростью

3.2.5 Соблюдение дистанции между воздушными судами

3.3 Система сбора и подготовки исходных данных.

3.3.1 Состав исходных данных

3.3.2 Источники информации.

3.3.3 Процесс подготовки исходных данных.

3.3.4 Статистические данные по работе аэропорта.

3.3.5 Подготовка данных по сети маршрутов руления ВС

3.3.6 Подготовка данных по расписаниям движения воздушных судов.

3.3.7 Типовые сценарии функционирования аэропорта

3.4 Структура модели наземного движения воздушных судов

3.4.1 Модель рулежной сети.

3.4.2 Модель воздушного судна.

3.4.3 Модель диспетчера воздушной зоны.

3.4.4 Диспетчер старта и посадки.

3.4.5 Диспетчер руления.

3.5 Поведение модели в динамике (процессы).

3.5.1 Моделирование движения воздушного судна по маршруту

3.5.2 Управление скоростью, дистанция между воздушными судами.

3.5.3 Процесс управления взлетами воздушных судов

3.5.4 Порождение воздушных судов

3.6 Программный комплекс.

3.6.1 Подсистема имитации.

3.6.2 Редактор рулежной сети.

3.6.3 Редактор расписаний полетов.

3.6.4 Редактор сценариев

3.6.5 Подсистема статистики

3.6.6 Подсистема визуализации.

3.7 Анализ адекватности.

3.7.1 Проверка адекватности модели.

3.7.2 Сравнительный анализ вариантов реконструкции

3.7.3 Оценка показателей пропускной способности аэропорта

3.7.4 Анализ результатов моделирования типовых сценариев

3.7.5 Выводы по результатам имитационного моделирования аэропорта.

3.8 Выводы.

Введение 2008 год, диссертация по информатике, вычислительной технике и управлению, Щетинин, Денис Вячеславович

Предмет исследования

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

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

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

Актуальность темы

Необходимость повышения эффективности технологий разработки, развитие информационных технологий, их широкое распространение и рост конкуренции на рынке информационных услуг заставляют сегодняшних разработчиков моделей работать в весьма жестких условиях. По сравнению с аналогичными проектами 70-х, 80-х и даже 90-х годов на порядки сокращены людские, временные и материальные ресурсы, которые могут быть привлечены для создания системы. Эти обстоятельства в сочетании с увеличением сложности моделируемых систем и требований к качеству имитационных программных комплексов делают весьма актуальной проблему повышения эффективности процесса разработки имитационных программных комплексов.

Необходимость обеспечения гибкости имитационных систем

Под термином «.гибкостью в данной работе понимается «готовность» программной системы к внесению изменений [9].

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

Таким образом, процесс разработки имитационных моделей (рис. 1) сопровождается постоянным изменением требований (и к самой модели, и к программному комплексу, в состав которого она входит).

Постановка задачи исследования ж.

Построение и реализация модели)

Шрактнческая эксплуатация

Требуется доработка]

Оценка адекватности модели V

Решение о развитии модели

Рис. 1. Итеративный характер процесса построения имитационной модели

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

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

Несостоятельность традиционных методологий разработки

Традиционно разработка сложных программных систем основывалась на водопадной модели жизненного цикла программного продукта [93]. И хотя эта модель явно не описывает организацию процесса разработки, на ее основе создавались методологии, ориентированные главным образом на подробное планирование всех этапов создания системы. Предлагалось на начальных стадиях разработки на основе тщательного и детального анализа предметной области выявлять все задачи разработки, ориентируясь на них разрабатывать архитектуру и дизайн системы. Все результаты, полученные на каждом из этапов, должны быть подробно задокументированы, и эта документация в дальнейшем используется на этапах кодирования, тестирования и ввода в эксплуатацию. При такой организации каждый следующий этап очень сильно зависит от результатов, полученных ранее. Соответственно, возврат на один или несколько шагов назад оказывается весьма дорогостоящей операцией, поскольку может потребовать пересмотра целого ряда уже решенных задач. В связи с этим такого рода методологии часто характеризуются как тяжеловесные (из-за большой инертности) и прогнозирующие (так как приходится заранее предугадывать все нюансы разработки) [68].

Очень часто описанная организация процесса разработки требует привлечения больших коллективов разработчиков (включающих в себя аналитиков, постановщиков задачи, архитекторов, проектировщиков, программистов, тестировщиков, технических писателей, менеджеров и т.д.), и приводит к весьма большим временным и материальным затратам. Но, самое главное, использование прогнозирующих методологий практически не обеспечивает возможности внесения существенных изменений в требования по ходу разработки. В современных условиях такой подход часто не оправдывает себя. Сегодня заказчики пе могут позволить себе ждать выхода программного продукта в течение 2 - 3-х лет, или новой версии в течении месяцев. Система должна приниматься в эксплуатацию и начинать приносить пользу уже через несколько месяцев после старта проекта, а важные изменения в дальнейшем должны вносится в течение нескольких недель или даже дней. В противном случае заказчик будет вынужден принимать управляющие решения без имитационного моделирования.

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

Так, основными направлениями исследований по повышению эффективности технологии имитационного моделирования было снижение трудоемкости построения моделей за счет использования инструментальных средств: специализированных языков [25, 41] и сред моделирования (GPSS [39, 73], Simplex3 [42], AnyLogic [22] и многих других). В рамках этого подхода были получены весьма значительные результаты, некоторые из которых стали заметными вехами в истории всей отрасли информационных технологий и определили ее развитие на годы вперед [82, 99, 102]. Именно имитационное моделирование стало полигоном для многих современных методов и технологий программирования (в качестве примера можно выделить Simula-67, который стал прародителем объектно-ориентированного программирования).

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

Потенциал гибких методологий

Приходится констатировать, что па сегодняшний день наметилось существенное отставание имитационного моделирования от других областей информационных технологий и программирования, где проблема гибкости решается на методологическом уровне. Во второй половине 90-х гг. основные подходы к решению этих проблем были сформулированы и опубликованы в виде манифеста гибких технологий [81]. Данное направление, а также предложенные подходы достаточно быстро были признаны актуальными и перспективными, начались масштабные исследования по этой теме. К настоящему времени сформировался уже целый ряд гибких методологий [68], которые нашли нашли свое применение на практике в конкретных областях: прикладные программные комплексы, базы данных, сетевые технологии, web-сервисы, разработка пользовательских интерфейсов и т.д.

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

Второй аспект проблемы — технический — связан непосредственно с программированием, которое можно понимать как перевод плохо формализованных и неструктурированных требований, предъявляемых к программному продукту, на формализованный компьютерный язык. Здесь возникают такие проблемы, как разработка соответствующей программной архитектуры, распределения функциональности между программными модулями, обеспечения эффективного взаимодействия между ними, выбора и реализации алгоритмов, контроля изменений в программном коде и т.д. Среди различных подходов и методов, призванных обеспечить гибкость программного кода в техническом аспекте, выделяется методология управляемой тестами разработки (Test-Driven Development), синтезирующая в себе такие методы как «проектирование в коде», «сначала тесты», «постоянная переработка кода». Данный подход, разработанный около 10 лет назад, уже достаточно хорошо зарекомендовал себя и широко применяется на практике. Однако, вопрос использования данной методологии в имитационном моделировании остается малоизученным.

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

Обзор литературы

Проблематика имитационного моделирования весьма подробно и глубоко рассматривается Шенноном [41]. Многие более поздние учебники и монографии [64, 35, 22] повторяют изложенные здесь идеи, подходы и оценки.

В качестве одной из основных проблем, ограничивающих применение имитационного моделирования, выделяется высокая стоимость (и в материальном, и во временном выражении) [41, стр. 26]. Причем одними из самых затратных называются проектирование, усовершенствование и реализация имитационной модели [41, стр. 158]. При этом особо подчеркивается эволюционный характер процесса конструирования [41, стр. 35] и выдвигаются требования адаптивности, возможности постепенного изменения (наряду с требованиями простоты и удобства использования) [41, стр. 37]. Однако, детально рассматривая организационные аспекты имитационного моделирования [41, гл. 7], в технических вопросах построения модели Шеннон ограничивается лишь подробным анализом задачи выбора языка моделирования и несколькими предложениями, носящими, скорее, рекомендательный характер [41, стр. 286 - 289]: разрабатываемая система должна строиться по принципу модульности и быть хорошо документирована.

По поводу документирования следует заметить следующее. Безусловно, документация к системе необходима. Однако, составление документации и (особенно) поддержание ее в актуальном состоянии в процессе разработки требует времени и сил, часто весьма значительных. Поэтому требуется найти баланс между теми преимуществами, которые дает подробная документация к системе, и затратами, которые потребуются для ее составления и сопровождения. При этом накопленный опыт [50, 68] показывает, что документирование само по себе не решает проблем, возникающих в процессе разработки сложных систем в условиях изменяющихся требований.

Модульное построение сложных систем на сегодняшний день — общепризнанный подход. Кстати, немаловажную роль в этом признании сыграли исследования в области имитационного моделирования. Однако методы построения модульных систем и их эффективность до сих пор являются предметом изучения и споров. В имитационном моделировании эта проблема также стоит весьма остро: Как найти адекватное разбиение на модули, обеспечивающее их дальнейшее взаимодействие в единой системе? Как преодолеть проблему нелинейного роста сложности системы [8, 12] при увеличении количества модулей? Как контролировать правильность работы отдельных модулей и системы в целом? Очевидно, ответы на эти вопросы и, собственно, построение сложных систем являются задачами творческими. Неслучайно в названии книги Шеннопа и одного из разделов в ней [41, стр. 33 - 35] присутствует слово «искусство». Тем не менее, решение этой проблемы в каждом конкретном случае может и должно базироваться на общих принципах и подходах, использовать известные и проверенные методы, поддерживаться на методологическом уровне. Но и в «классической», и в современной литературе по имитационному моделированию данному аспекту уделяется недостаточно внимания. Так, в [35] положения из книги Шеннопа дополняются лишь кратким изложением принципов минимизации сложности при формализации задачи и загрубления модели низшего уровня при композиции моделей. В [64] проблема программной реализации сводится, главным образом, к задаче выбора языка моделирования.

В [95] процесс разработки предлагается организовать по принципам, очень близким к гибким методологиям («Start small - Improve incrementally - Test frequently - Backtrack/simplify). Однако и здесь необходимость итеративной организации процесса разработки имитационных моделей просто констатируется, но подробно возникающие при этом проблемы и методы их решения не рассматриваются.

В [103] для решения проблем неопределенности требований, поиска баланса между точностью и простотой, адекватности и т.п. предлагается использовать методологию быстрого прототипирования. Идея заключается в разбиении процесса имитационного моделирования на два этапа. На первом создается прототип — упрощенная модель, которая создается исключительно с целью предварительного ознакомления пользователей с возможностями имитационного моделирования, уточнения задачи и выявления требований к системе. Эта модель внедряется, и по результатам ее практической апробации принимается решение о необходимости разработки более точной и развитой основной модели, выдвигаются и документируются требования к ней. По этой документации па втором этапе создается новая система, причем (в общем случае) она разрабатывается расширенной или вообще новой командой разработчиков, с использованием другого языка и среды моделирования, на основе документации, описывающей поведение прототипа и необходимые коррективы.

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

• Между этапами существует значительный временной разрыв, равный времени, необходимому для анализа результатов практического использования прототипа, выдвижения и формализации новых требований, реализации основной модели по ним и ее внедрения. За это время могут измениться условия работы заказчика, что повлечет за собой изменения в решаемых им задачах, в требованиях к разрабатываемой системе и, в конечном итоге, потере актуальности всего проекта

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

• Отсутствует преемственность (повторное использование) решений, найденных при реализации прототипа. Это также увеличивает общее время и стоимость проекта

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

Гибкие методологии призваны устранить эти и подобные недостатки [81, 9]. Развивая идею итерационного подхода, они создают необходимые условия для обеспечения эффективности разработки методом «от простого к сложному» за счет целого спектра методик, описывающих как организационные вопросы (обеспечение тесного и плодотворного взаимодействия между заказчиком и разработчиками, обеспечения соответствующего психологического климата внутри команды разработчиков, планирования и управления процессом разработки), так и технические аспекты, связанные непосредственно с проблемами программирования. К категории технических методологий следует прежде всего отнести методологию управляемой тестами разработки (Test-Driven Development, TDD), описанную Кентом Беком [10, 58, 60]. В специальной литературе достаточно широко представлены как базовые методы и принципы (например, «сначала тесты» [98], модульное тестирование [75, 74], регрессионное тестирование [92], автоматизация тестирования [104], рефакторииг [89, 63, 40]), так и сама методология [55, 105].

Эффективность данной методологии на сегодняшний день остается предметом изучения. Количественная оценка эффективности этой, или л юбой другой, методологии — весьма сложная задача. Во-первых, организация даже одного эксперимента, адекватно повторяющего условия реальной разработки, требует очень больших временных и материальных затрат. Получение репрезентативных статистических данных в этих условиях весьма проблематично. Во-вторых, эксперименты должны быть организованы таким образом, чтобы оценивать именно отличительные качества исследуемой методологии. Для TDD это, прежде всего, — анализ и проектирование в коде через разработку тестов. Повышение надежности программ, высокая степень покрытия программного кода тестами — это лишь дополнительный, даже второстепенный эффект. Важно, чтобы исследователь хорошо осознавал потенциальные положительные и отрицательные качества методологии. Как показывает практика, это далеко не всегда так. Кроме того, в реальной разработке огромную роль играет личностный фактор (интуиция и опыт отдельных разработчиков, их сплоченность в единую команду, владение конкретной методологией, соответствующими инструментами и т.д.). Исключить этот фактор из оценки практически невозможно, да и вряд ли целесообразно [86].

В проведенных по данному вопросу исследованиях далеко ие всегда оценивались именно основные аспекты TDD [72, 66]. Многие исследователи рассматривали только часть методологии [87, 106, 72, 65, 66]. Часто эксперименты не были обеспечены достаточными и надежными данными, носили предварительный характер [65, 87]. Полученные результаты во многом противоречат друг другу и, в конечном итоге, к сожалению, пока не претендуют на высокую степень достоверности.

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

Однако, возможности использования и эффективность в имитационном моделировании гибких методологий вообще и TDD в частности остаются малоизученными. В существующих публикациях по данной теме [70, 52] основное внимание уделяется организационным вопросам. Таким образом, технические проблемы, возникающие при итеративной разработке имитационных моделей, до сих пор не исследованы.

Цель работы

Цель работы — повышение эффективности разработки систем имитационного моделирования за счет обеспечения гибкости их программной реализации.

Предлагаемый подход к решению

Как отмечалось выше, для достижения поставленной цели предлагается использовать идеи и принципы гибких методологий, ориентированных на обеспечение эффективной разработки в условиях изменяющихся требований. Гибкие методологии позволяют получить [68, 9, 58]:

• более высокую частоту выпуска промежуточных версий

• высокую степень интерактивности взаимодействия клиент-разработчик

• снижение временных и материальных затрат при поступательном развитии модели «от простого к сложному» за счет более полного использования результатов (программного кода), полученных на предыдущих итерациях.

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

Предлагаемый подход основывается на использовании методологии Test-Driven Development (управляемой тестами разработки), фокусирующейся на инженерно-технических аспектах разработки программного обеспечения. Данная методология предлагает управлять процессом разработки с помощью постоянно развивающейся системы спецификаций, записанных в виде автоматических программных тестов. За счет этого данный подход позволяет:

• перевести процесс отражения требований в программный код на более формализованный уровень;

• организовать итеративную разработку, обеспечивая контроль изменений на всех этапах от формализации требований до их воплощения в программном коде;

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

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

Но применение данной методологии в такой специфической области как имитационное моделирование сталкивается с целым рядом проблем, в частности:

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

• наличие динамики осложняет создание тестов

• в тестах и при их реализации необходимо решать проблемы, связанные с наличием в системе множества параллельных (относительно модельного времени) процессов

• стохастический характер моделирования значительно усложняет проблему формулирования условий тестов

• наличие различных, часто противоречащих друг другу, точек зрения по вопросу адекватности модели также может затруднить формализованную постановку задач

• большие объемы данных, характеризующие поведение системы, могут привести к большим, сложным для понимания и модификации тестам

• трудности с получением точных данных, необходимых при создании тестов

• необходимость интеграции имитационной модели в существующую информационную инфраструктуру заказчика и/или параллельно разрабатываемый программный комплекс.

В данной работе рассматриваются эти проблемы и предлагаются пути их разрешения.

Новое решение в области технологии имитационного моделирования требует не только теоретического обоснования, но и проведения экспериментальных исследований на реальном проекте сложной системы моделирования. Такой проект должен стать, с одной стороны, полигоном для апробации предлагаемых принципов и методов, основой для их уточнения и отработки деталей их реализации, а с другой стороны — испытательным и демонстрационным стендом для оценки достоверности, эффективности и обоснованности предлагаемых подходов.

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

Таким образом, в работе теоретико-экспериментальным методом исследуется возможность применения гибких методологий разработки и конкретно методологии Test-Driven Development 1 в имитационном моделировании. Материалом эксперимента при этом является модель аэропорта.

Задачи исследования

В соответствии с выбранным подходом для достижения поставленной цели необходимо решить следующие задачи:

• Провести теоретическое обоснование использования гибких методологий в имитационном моделировании дискретных систем

• Разработать метод управляемого тестами имитационного моделирования

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

• Экспериментально показать практическую эффективность предложенного метода на примере реального, полномасштабного имитационного программного комплекса.

Результаты, выносимые на защиту

На защиту выносятся следующие результаты исследования:

• Метод управляемого тестами имитационного моделирования

• Имитационная модель наземного движения воздушных судов по летному полю аэропорта и программный комплекс для проведения имитационных экспериментов с ней, построенные на основе методологии управляемой тестами разработки

• Методика сбора и подготовки исходных данных для построения направляющих тестов на примере имитационной модели наземного движения воздушных судов.

Научная новизна

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

В контексте разработки имитационных программных комплексов с использованием методологии Test-Driven Development будет использоваться термин управляемая тестами имитационная система

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

Практическая значимость

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

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

Апробация

Представленные в работе результаты докладывались и обсуждались на 1-ой и П-ой всероссийских конференциях «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках» (Санкт-Петербург, 23 - 24 октября 2003 г. и 19 - 21 октября 2005 г. соответственно), конференции «Интеллектуализация обрабокти информации» (Алушта, Украина, 14 - 19 июня 2004 г.), на семинарах в ВЦ РАН и ТвГУ.

Публикации

По теме диссертации опубликовано 7 работ, в том числе, 1 работа в рецензируемом журнале, рекомендуемом ВАК, — [46] и 6 работ в других изданиях: [18, 43, 44, 45, 47, 48].

Внедрение результатов

Выносимые на защиту методы были реализованы, исследованы и использованы для решения прикладных задач в ходе работ по проекту реконструкции международных аэропортов «Шереметьево», «Домодедово».

Структура работы

Структура работы определяется задачами, которые необходимо было решить в ходе исследования.

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

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

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

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

Далее рассматривается архитектура разработанного программного комплекса — его основные подсистемы, их назначение, схема взаимодействия и т.д. Основное внимание при этом уделяется внутреннему устройству имитационной модели наземного движения воздушных судов. Модель описывается в двух аспектах: «в статике» — основные компоненты, их структура и взаимосвязи, и «в динамике» — процессы, поведение отдельных объектов во времени, взаимодействие между ними.

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

В заключении подводятся итоги работы:

• Представлен метод управляемого тестами имитационного моделирования, основанный на идеях и принципах гибких технологий программирования и, в частности, методологии Test-Driven Development (TDD)

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

Заключение диссертация на тему "Управляемая тестами система имитационного моделирования наземного движения воздушных судов"

3.8. Выводы

Процесс разработки имитационной модели аэропорта в соответствии со стратегией от «простого к сложному» включает в себя несколько итераций.

Методология TDD позволяет организовать такую итеративную разработку, обеспечивая, в частности, следующие возможности: • на формализованном уровне специфицировать задачи, решаемые на каждой итерации, в программном коде в виде автоматизированного теста

• управлять процессом разработки, варьируя последовательность решаемых задач, их размер на каждой итерации и их спецификацию в создаваемых тестах

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

• контролировать качество программного кода, оценивая трудоемкость создания теста для очередной задачи и вовремя улучшая дизайн системы

• использовать созданные тесты в качестве технической документации к разрабатываемой системе

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

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

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

Заключение

В работе представлен метод управляемого тестами имитационного моделирования, основанный на идеях и принципах гибких технологий программирования и, в частности, методологии Test-Driven Development (TDD). Метод обеспечивает возможность эффективно организовывать эволюционную (итеративную) разработку имитационных моделей сложных систем «от простого к сложному». В рамках исследования были поставлены и решены следующие задачи:

• Проведено теоретическое обоснование использования гибких методологий в имитационном моделировании дискретных систем

• Разработан метод управляемого тестами имитационного моделирования

• На примере разработки имитационного программного комплекса моделирования наземного движения воздушных судов экспериментально показана практическая эффективность данного метода

• В рамках разработки данного имитационного программного комплекса решены следующие задачи:

Проведен анализ предметной области, выбраны и формализованы показатели качества работы АП, обосновано применение гибких методологий разработки

Разработана методика сбора и подготовки исходных данных для построения направляющих тестов

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

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

Таким образом, эффективность метода обоснована как теоретически, так и опытно-экспериментальным путем.

Полученные результаты использованы на практике при сравнительном анализе вариантов реконструкции международного аэропорта «Шереметьево», а также при планировании реконструкции международного аэропорта «Домодедово».

Библиография Щетинин, Денис Вячеславович, диссертация по теме Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

1. Алгоритм Дейкстры. Ь^р://ги^1к1рес11а.о^/у1к1/Алгоритм Дейкстры.

2. Аллеи, Э. Типичные ошибки проектирования. Библиотека программиста / Э. Аллен.— СПб.: Питер, 2003.

3. Арнольд, В. И. «Жесткие» и «мягкие» математические модели / В. И. Арнольд. М.: МЦНМО, 2004.

4. Ауэр, К. Экстремальное программирование: постановка процесса / К. Ауэр, Р. Миллер. СПб.: Питер, 2002.

5. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Д. Хопкрофт, Д. Ульман. — Москва: Мир, 1979.

6. Ашфорд, Н. Проектирование аэропортов / Н. Ашфорд, П. X. Райт. — М.: Транспорт, 1988.

7. Ашфорд, Н. Функционирование аэропорта / Н. Ашфорд, X. П. М. Стентон, К. А. Мур. — М.: Транспорт, 1990.

8. Бадд., Т. Объектно-ориентированное программирование в действии: Перев. с англ. / Т. Бадд. — СПб.: Питер, 1997.

9. Бек, К. Экстремальное программирование / К. Бек. — СПб.: Питер, 2002.

10. Бек, К. Экстремальное программирование. Разработка через тестирование / К. Бек. СПб.: Питер, 2003.

11. Боровков, А. А. Математическая статистика / А. А. Боровков, — М.: Наука., 1984.

12. Буч, Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд.: Пер. с англ. / Г. Буч.— М.: «Издательство Бином», СПб: «Невский диалект», 1998.

13. Вептцель, Е. С. Исследование операций. Задачи, принципы, методология. Учеб. пособие для студ. втузов / Е. С. Вентцель. — М.: Высш. шк, 2001.

14. Дал, О. И. Симула. Язык для программирования и описания систем с дискретными событиями / О. И. Дал, К. Нигард. — АН ССР, Центральный экономико-математический институт, Москва, 1966.

15. Иванов, В. Аэропроект и аэропорты / В. Иванов; Воздушный транспорт. — М., 1998.

16. Ивченко, Г. И. Теория массового обслуживания: Учеб. пособие для вузов. / Г. И. Ивченко, В. Каштанов, И. Коваленко. — М.: Высш. школа, 1982.

17. Изыскание и проектирование аэродромов / Под ред. Г. И. Глушкова. — М.: Транспорт, 1992.

18. Имитационное моделирование аэропорта — инструмент обоснования решений / Д. Щетинин, JI. Местецкий, А. Исаев, А. Федоров // Аэропорт Партнер. — 2002. — № 5-6.

19. Инструкции по производству полетов в районе аэродрома Шереметьево.

20. Исследование процессов и разработка программного комплекса, моделирующего наземное движение ВС в аэропорту Шереметьево. — М.: ОАО Научно-исследовательский институт экономики авиационной промышленности, 2002.

21. Калашников, В. В. Математические методы построения стохастических моделей обслуживания / В. В. Калашников, Р. С.Т. — М.: Наука, 1988.

22. Карпов, Ю. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5 / Ю. Карпов, — СПб.: БХВ-Петербург, 2005.

23. Карта-схема летного поля «Реконструкция а/п Шереметьево».

24. Кауфман, В. Ш. Языки программирования. Концепции и принципы / В. Ш. Кауфман. — М.: Радио и связь, 1993.

25. Киндлер, Е. Языки моделирования: Пер. с чеш. / Е. Киндлер. — М.: Энергоатомиздат, 1985.26