г. Новосибирск, 15-17 октября 2012 г.

Попел Е.В.  

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

Среди существующих моделей движения людей имеется многочисленный класс моделей, в которых главной “движущей силой” является минимизация расстояния до цели (выхода). Информация о расстоянии из каждой точки рассматриваемой плоской области до ближайшего выхода хранится, в так называемом, поле расстояний S. Это поле является статическим и не зависит от положения людей. Для вычисления поля S вся область моделирования покрывается двумерной ортогональной сеткой с равными ребрами фиксированного размера, для каждого узла которой рассчитываются расстояния до выходов. Если узел сетки попал на непроходимый участок (такой как мебель, стена), то информация об этом также хранится в поле расстояний – например, в качестве расстояния до выхода берется либо отрицательное либо очень большое число. Шаг сетки определяет точность расчета поля S и качество моделирования движения людей, поэтому наилучшим вариантом является мелкая сетка. Но тогда процедура расчета расстояний занимает много времени и требует немалых аппаратных ресурсов. В тоже время рассчитывать поле расстояний необходимо каждый раз, когда вносятся какие-либо изменения в планировку здания или при «перестановке» мебели. В данной работе решается вопрос о выборе оптимального алгоритма для расчета такого поля расстояний для области произвольной формы и рассматриваются возможные пути для его упрощения и увеличения скорости расчета.
Сопутствующей задачей является выбор формата хранения информации о поле расстояний. Прямой путь – хранить в виде двумерного массива, не является оптимальным в общем случае. Область моделирования может иметь произвольную форму, и, при покрытии такой области непрерывной сеткой, площадь сеточного пространства оказывается больше площади области моделирования (в практических задачах речь идет площадях, измеряемых  десятками тысяч квадратных метров). В результате будет отводится дисковое пространство под ненужную для дальнейшего моделирования информацию. При использовании поля, сохраненного таким способом, необходимо выделять больше оперативной памяти. Вопрос об определении оптимального формата хранения поля расстояний также рассматривается в данной работе.

Тезисы доклада:abstracts_138118_ru.pdf
Файл с полным текстом: ym2012_article_Popel2007.pdf


К списку докладов

Комментарии

Имя:
Код подтверждения: