Содержание материала

4.2. Алгоритм.

В самом начале описания хотелось бы ввести понятие “зазор”. Оно не содержит ничего нового, но значительно упрощает изложение ряда вопросов. Зазор – промежуток времени в плане между окончанием одного действия и началом следующего; либо между началом (окончанием) первого (последнего) действия и границей горизонта планирования. Зазор может принимать значения от нуля до величины всего горизонта планирования ([0; ГП]).

В общем виде алгоритм планирования выглядит следующим образом (рис. 1):

 

planning1Рисунок 1. Блок-схема работы алгоритма планирования.

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

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

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

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

При этом агент соблюдает приоритет: сначала он пытается уместить действие в пересечение желаемого (ЖД) и допустимого (ДД) диапазонов, – тем самым он пытается запланировать действие не только на возможное, но и на удобное время. Затем, если пересечение оказывается недостаточным по продолжительности (чтобы вместить действие), то агент ориентируется только на ДД. Если же действие не умещается и в ДД, то оно исключается из рассмотрения.

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

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

 

planning2Рисунок 2. Блок-схема процедуры определения возможности внесения действия в план.

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

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

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

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

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

 

planning3Рисунок 3. Блок-схема процедуры смешанного поиска.

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

planning4

Рис. 4. Возможное вытеснение действия в целевой зазор при переносе

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

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

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

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

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

 

planning5Рисунок 5. Блок-схема процедуры определения достаточности зазора.

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

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

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

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

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

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

Чтобы оставить комментарий, необходимо зарегистрироваться

© 2015 humanmodel.ru