idorobots / mall-sim

A simulation of movement of people at a shopping mall using Social Distances. An AGH-UST project.

Shopping mall Simulation

A discrete simulation of pedestrian movement at a shopping mall using Social Distances.

mall-sim's Issues

Actor search

A quick way to find all the actors in a rectangle, the nearest actors to a given point and such. Details depend on shopping mall and actor models.

Path rendering

Actor path rendering and optionally traffic visualization. The more eye-candy the better.

Goal system

Concrete implementation of the goal system.

Crowding

Actors should crowd in certian places (such as tight exits, and highly atractive places).

GUI design

We need a pretty GUI with all kinds of eye-candy and nice parameter selectors.

The main window consist of two panels: one with a draggable grid and another with parameters' summary.

Można wyświetlać "jedno piętro sklepu nad drugim", tzn. np. scroll kółkiem myszy powodowałby przejście na inny poziom.

Shopping mall rendering

A simple visualization of a shopping mall loaded by the resource manager.

Actor movement & behaviour model

We require a well-defined model of actor movement & behaviour - the cornerstone of this simulation.

The model should describe both macro (i.e. path planning) and micro (i.e. single-step decision making) actor behaviour, as well as the abstract representation of the movement (continous vs discrete, actor vs cellular automata).

Poziom operacyjny

Jak zauważył dr Wąs, ciągły model ruchu słabo się skaluje, stąd CA na poziomie operacyjnym wydają się dobrym rozwiązaniem.

Implementacja podstawowego mechanizmu poruszania się może opierać się na dwóch modelach:

• Modeling Four Directional Pedestrian Movements
• Cellular automata microsimulation for modeling bi-directional pedestrian walkways

Idea mikrosymulacji CA-Ped (2 kierunki):
Pieszy identyfikuje ilość wolnego miejsca przed sobą i wybiera "pas ruchu" umożliwiający poruszanie się z największą prędkością. W przypadku ryzyka kolizji zmienia pas ruchu, najchętniej ustawiając się za inną osobą idącą w tym samym kierunku, przeciska się obok idącej z naprzeciwka osoby bądź czeka na działanie podjęte przez drugą stronę.

Aby uniknać efektu ciągłego zachodzenia drogi osobom idącym z naprzeciwka (gdy dwa cele znajdują się po dwóch różnych stronach alejki) można ustalić pewną wartość progową różnicy między azymutem kierunku ruchu, a azymutem kierunku celu - dopiero gdy zostanie przekroczona, pieszy zaczyna zbaczać z trasy "na wprost" (tj. zaczyna zmieniać "pasy ruchu").

Poziom taktyczny

Na poziomie taktycznym galeria reprezentowana jest jako graf nieskierowany o ważonych krawędziach. Węzły odpowiadają skrzyżowaniom ciągów komunikacyjnych, a krawędzie łączą ze sobą te węzły, które są wzajemne osiągalne (tj. bez natrafiania na przeszkody, zakładając poruszanie się po linii idąc od jednego do drugiego). Waga krawędzi odpowiada odległości pomiędzy węzłami.

Pieszy wybiera drogę do celu poprzez szereg punktów pośrednich, starając się przy tym minimalizować konieczną do przebycia odległość.
Obecność atraktorów może wpłynąć na chwilową zmianę celu.

Some observed behaviors

• Buy something to eat even if you are not so hungry.
• Use your mobile to text while walking (sometimes stop randomly).
• When passing by a shopping window you watch but not slow down.
• People enter the shop usually through the middle part of an entrance.
• Couples tend to walk shoulder oto shoulder (= 2 persons / 2 tiles)
• A standard lane is ~2 tiles wide.
• If there is enough space we prefer to give other people a wide berth.
• Standing/stopping people try not to cause congestion.
• Stages of entering a shop: slow down, stop (roamers only), enter
• When leaving a shop people try to reach their lane as quickly as possible (ie. there are not many people sneaking near the wall).
• Customers often walk around a booth to see the whole offer.
• The only sitution when a couple split up is when a girl want to look a little bit longer on shopping window.
• People stop to think about their further way only on intersections.
• Couples walk slower than pairs.
• Right-handed movement is a culture-dependant yet well established habit (?). Even if a lane is completely free pedestrians prefer to use the right side.

Usually a group consists of 2-3 persons (rarely 4):

• 2 persons: linear formation
• 3 persons: linear formation (sometimes triangular)
• 4 persons: rectangular formation (2x2)

How to avoid collision:

• pair: eliminate a gap between people; form a column
• couple: it's a problem of the third person!
• 3 persons: the outermist person "hides" behind the middle one
• 4 persons: eliminate a gap

"Field of View" eg. rectangular area used by actors to perceive the reality (ie. to choose path, avoid colisions etc.)

GUI implementation

A concrete implementation of the GUI.

External actor representation

An actor file format and loading that will include various actor types as defined in the actor model.

Goal system

We need a simple actor goal system - a list of places to visit.

Shopping mall representation

We need a well-defined internal and external mall representation.

We can identify the following "features" of a mall:

• walkable area
• walls
• escalator
• elevator
• goal (attractor)
• sub-goal (used for routing)
• link /between sub-goals/ (used for routing, calculated from other data - each (sub)goal is connected with all neighbors accessible by following a straight line)
• mall's entrance (generate/remove customers)

"Waiting areas" (eg. benches) can be modelled as a goal with a small radius, relatively high attraction and long waiting time.

Examples of shops in a mall:

• small catering: bakeshop, ice-cream kiosk
• services: photograph, hairdresser, laundry, xero, optician
• offices: post, bank
• other: restroom for kids
• "street stalls": gifts, 101 knick-knacks, accessories for mobiles, TV providers
• shops: fashion, watches, shoes, cosmetics, bookshop, zoology, newspapers, pharmacy, florist's
• catering: bistro, restaurant
• furnishings: furniture, RTV

Parameters of shops relevant to the simulation:

• size and quality of a shop window
• branded?

Reprezentacja w programie

Pole zawiera mapowanie atraktor->wartość przyciągania (dla danej płytki), obliczane w chwili ładowania mapy.

Kodowanie w pliku

A map of a mall is stored in a simple graphics format (eg. BMP), where each pixel represents a cell in a CA grid. It may be useful to use each of three color components separately to encode different aspects of a cell (np. R = typ obiektu, G i B = parametry obiektu danego typu)

Attractos' parameters are stored in property files and are linked with locations based on IDs.

Crowding & self-organization

We need to refine the actor model to add some traits of self-organization and crowding in tight places such as exits.

"Rubber-necking" and crowd atracting might be a fine idea aswell.

Social distances

We need a well-defined model of social interaction between actors - their distance preference in various situations and places (i.e. short distance will be accepted while in a queue, but not in other situations).

Walls tend to repel people (with a strength similar to those of other people). This may help us simulate an observed equal distribution of walkers across a street.

We may let user define a force formula (or choose from a given set of built-in functions).

Self-organization

The actor implementation should be adjusted to bare some traits of self-organization.

Rotation & transformation

The renderer should be able to rotate, zoom in and out of and drag arround the shopping mall view.

Misc stuff

Optionally we could look into various misc algorithms and actor behaviour models. Sky is the limit.

Actor rendering

A simple visualization of the actors.

Internal actor representation

An implementation of the actor model. Basic stuff such as position and "sleep-walking" for now.

Atrybuty

• położenie (na planszy, 2D)
• prędkość maksymalna
• mapa parametrów [1]
• lista celów
• aktualny kierunek ruchu [2]
• "pole siły" [3]

[1] Wszystkie aspekty społeczno-ekonomiczno-psychologiczne wpływające na zachowanie agenta (tj. można powiedzieć - zbiór stałych opisujących preferencje agenta).
[2] Istotne dla algorytmu Ped-4.
[3] Dla algorytmu Social Force. Może to być np. mapowanie zbioru punktów-offsetów (wzgl. aktualnej pozycji i z uwzględnieniem obrotu agenta) na wartość siły.

Atractors

Atractors should modify actors paths by grabbing their attention and pulling them closer for a set duration of time.

Atractor parameters:

• radius
• waiting time (duration)
• attraction

Atraktory nie są rozdzielone na różne klasy, tzn. że np. preferencje klienta nie mają wpływu na podatność na działanie atraktorów.

W dowolnym miejscu w promieniu atraktora może dojść do "wyzwolenia" jego działania, z tym że prawdopodobieństwo rośnie wraz ze zbliżaniem się do centrum (gdzie osiąga 100%). W takim przypadku trasa agenta zostaje zmodyfikowana: zostaje dodany nowy cel pośredni - atraktor.

Niektóre atraktory mogą operować na parametrach agenta (Visitor pattern).

Actor queueing

We need to refine the Mall representation and actor model to include queueing. This issue will identify and document the way to achieve this.

Kolejkowanie można rozwiązać poprzez traktowanie jej jak atraktora z odpowiednim gradientem (który z jednej strony będzie utrzymywał ludzi w kolumnie, z drugiej będzie niwelował siłę odpychania osoby stojącej przed danym agentem).

Internal mall representation

Internal Mall implementation with all basic operations.

Mall

Główna klasa reprezentująca galerię handlową.

Parametry:

• plansza (Board)
• sieć celów (GoalNetwork)
• lista "teleportów" (schody, windy itp.) (najprawdopodobniej klasostruktura)
• atraktory (Attractor)

Board

Klasa reprezentująca fizyczną strukturę galerii, tj. siatkę pól.

Parametry:

• tablica 2D komórek (Cell)

Operacje:

• Znajdowanie listy pieszych znajdujących się w zadanym sąsiedztwie. (Ponieważ informacja o położeniu pieszego jest dostępna zarówno poprzez planszę jak i przechowywana jako atrybut agenta, konieczne jest wprowadzenie dodatkowych metod do zmiany położenia.)
• Obliczanie gradientu dla planszy na podstawie atraktorów, ścian, ludzi itd. "Gradient" przechowywany jest jako rozkład pola potencjału i dopiero w chwili wywołania dla pola odpowiedniej metody zwracana jest faktyczna wartość gradientu, tj. znormalizowany rozkład prawdopodobieństwa w sąsiedztwie tego pola.

Cell

Klasa reprezentująca jedno pole siatki.

Parametry:

• typ pola
• pieszy
• mapa wartości pól potencjału
• typ algorytmu używanego do obliczania ruchu (dla pieszego stojącego na danym polu)

Operacje:
[brak]

GoalNetwork

Klasa reprezentująca sieć węzłów służących do "routingu".

Parametry:

• lista celów
• lista istniejących połączeń między celami

Operacje:

• znajdź sąsiada itp.

Attractor

Klasa opisująca atraktor.

Parametry:

• opis pola

Operacje:
[brak]

Atractors

Concrete implementation of atractors - places of increased likelihood of grabbing actors attention.

Agent representation

We need a well-defined internal and external actor type representation.

Actors should be defined as a set of attributes determining their goals and single-step behaviour. Each actor type should be loaded at runtime.

A set of predefined standard actor's parameters is defined in appropriate property files.
They are used as a base for the creation of real actors (parameters' values are modified in a random fashion to reflect the diversity of the real world).

Atrybuty

• położenie (na planszy, 2D)
• prędkość maksymalna
• mapa parametrów
• lista celów

Typical shopping speed:

• vigorous adult: 6km/h
• "normal" adult: 4,5km/h
• pensioners, "roamers": 2,5km/h

Parametry (w rozszerzonej wersji symulacji)

• sex: influences eg. amount of time spend on window shopping
• age (youth/adult/pensioner)
• dynamism of walking (acceleration etc.)
• wealth

Collision avoidance

One of actors single-step behaviours. It should be defined in terms of actor goals and path finding.

Actor types

Concrete implementation of various actor types (depends on the actor model and design).

Atractors rendering

A simple visualization of the atractors and such (includes atractor stub without the logic).

Path finding & pursuing

Actors should find optimal paths to their goals and follow them with no respect to collisions etc.

Queueing

Actors should stand in a line in certian places.

Path finding

We need a path-finding strategy for actors.

According to their goals actors will generate dynamically changing paths. This issue needs to identify and document various needed algoritms to achieve this.

Open issues:

• Shall we reroute if we identify a crowded area blocking our way? Or is it a marginal case (normally not present)?

Social Distances

Actors should prefer certian decisions taking Social Distances into account (i.e. waiting a bit instead of rushing through a crowded alley).

External mall representation

Well-defined mall file format and loading.