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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

Указанные проблемы существующих электронных календарей делают в итоге весьма сложными и трудоёмкими операции планирования и не позволяют пользователям эффективно управлять своим временем. В то же время стремительный технический прогресс в области Интернет-систем, семантического веба и мультиагентных технологий, мобильной связи, спутниковой GPS/ГЛОНАСС-навигации и ряда других в последнее время открывает новые возможности для решения рассматриваемых проблем.

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

В данной работе описываются результаты применения мультиагентных технологий для решения поставленной задачи, которые были получены при выполнении работ по теме «Разработка мультиагентной системы динамического планирования персональных задач для мобильных пользователей» (шифр «2009-04-1.4-00-07-012»), выполняемой в рамках ФЦНТП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы».

Обзор существующих решений по планированию персональных задач

Экспериментальное исследование и апробация существующих на сегодняшний день на рынке систем планирования персональных задач и электронных календарей, например [1, 2], позволили выявить основные проблемы, возникающие при использовании данных систем. Все эти системы предназначены в основном для «ручного» управления расписаниями. Традиционные системы вроде Microsoft Outlook или календари на любом сотовом телефоне, по своей сути, не позволяют осуществлять автоматическое планирование задач, а служат лишь для задания времени наступления того или иного события и выдачи напоминания пользователю, т.е. позволяют в основном только помнить о событии. Помимо Microsoft Outlook, примерами подобного рода систем являются настольные приложения вроде Mozilla Sunbird, pNotes или Leader Task, а также активно развивающиеся в последнее время web-сервисы вроде Google Calendar, ориентированные на поддержку коллективной работы за счёт наличия разделяемого расписания работ или встреч.

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

- формирование различных отчётов (по времени, по стоимости задач, по загруженности пользователя в тот или иной период и т.д.);

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

- отображение плана в виде диаграммы Гантта;

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

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

- возможность привязки к денежным ресурсам (планирование суммы средств);

- настройка интерфейса (темы, расположение элементов);

- поддержка разных приоритетов задач (важные, критичные и т.д.);

- учет завершённости задач и поддержка версионности изменений;

- возможность визуально группировать задачи в календаре с использованием пользовательских иконок.

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

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

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

Подход к планированию персональных задач, основанный на использовании мультиагентных технологий и онтологий

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

Мультиагентные технологии [3, 4] позволяют решать проблемы, для которых характерны частые и непредсказуемые изменения и имеют место сложные зависимости между элементами. В отличие от традиционных систем, в которых решение ищется с помощью централизованных, последовательных и детерминированных алгоритмов, в мультиагентных системах решение достигается в результате распределённого взаимодействия множества агентов - автономных программных объектов, нацеленных на поиск, возможно, не столько полностью оптимального, сколько наилучшего из возможных решений на каждый момент времени.

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

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

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

- описание шаблонов задач с помощью онтологии;

- загрузка шаблонов типовых задач других пользователей из сети Интернет;

- добавление в расписание и обработка системой новых событий;

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

- планирование и перепланирование взаимосвязанных задач в реальном времени с визуализацией расписания с использованием средств ГЛОНАСС/GPS;

- взаимодействие с другими пользователями;

- поддержка несовместимости операций (например, нельзя одному человеку находиться в двух местах одновременно);

- отслеживание времени выполнения операций и контроль исполнения плана;

- интерфейсы для интеграции с наиболее распространёнными системами и сервисами по планированию;

- поддержка собственного формата файлов для хранения задач / событий.

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

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

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

- Мультиагентная система планирования персональных задач (персональный планировщик) представляет собой специальное клиентское приложение, состоящее из двух компонентов - серверного приложения для планирования персональных задач, формирования расписаний и пр. и специального клиентского приложения для мобильных устройств на базе о/с Microsoft Windows Mobile 5.0/6.0, используемого для предоставления доступа к серверному компоненту и ресурсам системы планирования.

- Интернет-портал онтологий и сервисов играет роль общедоступного ресурса для доступа к предоставляемым сервисам планирования задач базовыми агентами планирования, размещения онтологий пользовательских задач, создания новых шаблонов задач (templates), открытых для свободной загрузки пользователями (на базе Google-календаря).

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

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

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

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

- все задачи планируются на ресурсы. В рамках проекта ресурсом является только человек (пользователь). Задачи могут планироваться как на один ресурс (личная задача), так и на несколько ресурсов (групповая задача);

- под каждую задачу в сцене создаётся агент этой задачи;

- как только агент задачи получает управление, он «смотрит», должна ли его задача быть запланирована. Если у неё не стоит признак «не планировать» (в связи с тем, например, что пользователь ещё не определил предпочитаемое время, либо если задача ожидает какие-либо условия, а эти условия ещё не выполнились), то агент пытается запланировать задачу на указанное предпочитаемое время, которое либо задается явно пользователем, либо определяется некоторыми условиями;

- планирование осуществляется посредством создания «переходных точек» (Modification point) для задачи (точки «Начало» и «Конец» выполнения) в сцене для каждого ресурса;

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

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

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

Библиографический список

мобильный планирование пользователь мультиагентный

1. US Patent №7.418.482 - Web-based task assistants for wireless personal devices / http://www.patentstorm.us/patents/7418482.html

2. Тарасов В. Обзор Time Assist Pro - планировщика времени и персонального информационного менеджера / http://www.ixbt.com/soft/time-assist-pro.shtml

3. В.А. Виттих, П.О. Скобелев. Метод сопряженных взаимодействий для управления распределением ресурсов в реальном масштабе времени / Автометрия. - 2009. - №2. - С. 78-87.

4. Multi-Agent Real Time Scheduling System for Taxi Companies / Andrey Glaschenko, Anton Ivaschenko, George Rzevski, Petr Skobelev // AAMAS 2009, Budapest, Hungary. - 2009. - P. 29-36.

Размещено на Allbest.ru