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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1. Список задач в мобильном устройстве

Рис. 2. Графическое представление списка задач в мобильном устройстве

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

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

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

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

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

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

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

Рабочее место для редактирования базы знаний (онтологии)и настройки планировщика

Пользовательский интерфейс для персонального компьютера

Мобильный клиент для работы с личным расписанием

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

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

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

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

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

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

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

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

Компонент пользовательского интерфейса мобильного устройства представляет собой приложение для операционной системы W indows Mobile. Посредством данного компонента можно осуществлять поиск шаблонов, загрузку их в личное расписание, а также добавление/ редактирование/удаление «простых» задач (не загруженных из шаблонов) с мобильного клиента. Задачи можно посмотреть как в списке, так и в представлении диаграммы Гантта. Кроме того, посредством мобильного клиента можно осуществлять синхронизацию задач с Microsoft Outlook и Google Calendar.

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

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

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

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

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

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

• -    основные взаимозависимости между концептами – в виде отношений между концептами;

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

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

Реализация редактора онтологий представлена на рис. 4.

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

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

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

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

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

Реализация описываемого подхода, произведенная с использованием платформы.NET, предоставляет пользователю следующие возможности:

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

  

  Рис. 4. Редактор онтологии пользователя мобильного устройства

  
  

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

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

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

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

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

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

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

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

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

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

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

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

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

Для оценки качества расписания может использоваться ключевой показатель эффективности – key performance indicator (KPI) – например, суммарный бонус с учетом штрафов. На рис. 5 приведены показатели KPI для разных стратегий планирования: при большой плотности задач суммарный KPI снижается, так как все меньшее количество задач может попасть на свое предпочитаемое время, а также увеличиваются суммарные штрафы за опоздание.

Увеличение времени для поиска наилучшего решения свидетельствует о проработке большего количества опций. Также можно отметить колебания KPI при поиске вариантов плана в случае, когда наилучшее решение уже найдено.

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

• -    повысить эффективность планирования персональных задач;

  

  Отсчет времени

  
  
  

  Рис. 5. Зависимость KPI от времени планирования (отсчета) для случаев: с базовой комбинацией задач (а), повышения длительности на 50% (б) и повышения длительности на 100% (в) от базового варианта

  
  

• -    оперативно и гибко реагировать на непредвиденные события в реальном времени, своевременно изменяя расписание;

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

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

• -    контролировать исполнение плана в реальном времени;

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

Заключение

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

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

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