Method and apparatus of simulating movement of an autonomous entity through an environment

[0001] The present invention relates to a method of simulating movement of an autonomous entity through an environment, for particular but not exclusive use in a method of modelling pedestrian crowd movement.

[0002] A physical system may be considered as a collection of individual constituents interacting with each other and their surroundings. The constituents, usually referred to as “agents”, may be characterized by several attributes and modes of interaction.

[0003] Systems may or may not be self-contained and such systems are usually referred to as being “closed” and “open” respectively. Furthermore, if the interactions between agents are sufficiently complicated, then the system is said to be “complex”. Moreover, if agents are endowed with a feedback mechanism for perceiving and reacting to signals and thus adjust their behaviour or interaction mechanisms, then they are said to be “adaptive”.

[0004] A system comprising many interacting agents is commonly referred to as a “multi-agent complex system”. One example of such a system is a pedestrian crowd.

[0005] A multi-agent complex system may be considered from two different points of view. Either one may consider the collective patterns that characterize the system in its entirety or one may focus on interaction mechanisms at the level of each individual constituent. These approaches are referred to as “macroscopic” and “microscopic” formulations respectively.

[0006] It is known to use a macroscopic model to describe a pedestrian crowd as a quasi-uniform medium, such as a fluid, without regard to individual constituents. It is typically low-resolution and results in only rough estimates of bulk measures, such as flows and densities, under certain conditions. Thus, it treats a pedestrian crowd as a quasi-uniform continuous fluid rather than interacting individuals.

[0007] Such a model is best suited to situations involving large spaces and large, uniform crowds, where there are no rapid variations in conditions, little change in the landscape and little variety in the purpose and function of the environment. Under these conditions, a macroscopic model may provide a reasonable estimate of the densities and flows.

[0008] An example of a macroscopic model is given in “Forecasting the Flow of People” by K. Ando, H. Ota and T. Oki, Railway Research Review, volume 45, page 8 (1988).

[0009] However, a macroscopic model is poorly suited to situations involving multi-directional flows and varied pedestrian profiles, where there are complicated geometries, rich in structure, and where there are a multitude of rapidly changing conditions. Under these conditions, macroscopic models may be misleading and lead to erroneous conclusions.

[0010] Despite this drawback, many methods of modelling pedestrian movement, including those used to set safety standards for buildings and spaces, use macroscopic approaches.

[0011] In contrast, microscopic models address the behavior of individual agents.

[0012] Microscopic models, such as Cellular Automata and other heuristic rule-based models, use ad-hoc parameterizations based on arbitrary probabilistic and statistical rules. These models are higher-resolution in that they consider individual agents and short-range variations in conditions. They also exhibit dynamic and emergent behavior. Nevertheless, they have several drawbacks. They tend to rely on having a homogeneous space and identical individuals. They are also difficult to calibrate and validate and are also erratic and unreliable. In fact, microscopic models which cannot be calibrated using empirically measured data are of questionable utility for practical applications and predictions. Thus, although qualitatively plausible, they are not suited to practical applications. At best they are used for illustrative purposes only.

[0013] Attempts have been made to formulate better microscopic models and an example is described in “Simulating dynamical features of escape panic” by Dirk Helbing, Illés Farakas and Tamás Vicsek, Nature, volume 407, pages 487 to 490 (2000). However, these models are applied to a specific set of circumstances which allow simplification.

[0014] It is desirable to develop a method of simulating movement of an autonomous entity through an environment for use in a method of modelling pedestrian crowd movement which can allow for design challenges such as non-uniform spaces, a variety of user profiles, a multitude of agent choices, dynamic changes in environment and chances events.

[0015] The method can be used for designing venues, troubleshooting flow problems, operational management, setting and implementing safety standards and quality control.

[0016] The present invention seeks to provide a method of simulating movement of an autonomous entity through an environment.

[0017] According to the present invention there is provided a method of simulating movement of an autonomous entity through an environment, the method comprising providing a provisional path through a model of the environment from a current location to an intended destination, providing a profile for said autonomous entity, determining a preferred step towards said intended destination based upon said profile and said provisional path, determining a personal space around said autonomous entity, determining whether said preferred step is feasible by considering whether obstructions infringe said personal space.

[0018] This has the advantage of providing a more accurate simulation of movement.

[0019] If the preferred step is not feasible, then the method may further comprise determining a region in which to seek a compromise step and determining whether at least one compromise step is feasible.

[0020] This has the advantage that it reduces the computational effort needed to determine a compromise step.

[0021] The method may comprise choosing one of a plurality of compromise steps. The method may comprise determining said region includes adapting within said region in dependence upon at least one locally perceivable condition. The determining of the region may include adapting within said region in dependence upon memory of past conditions. The determining of the personal space may comprise defining a region in which absence of obstructions is sought. Obstructions may include other autonomous entities and fixed obstructions. The determining of the preferred step may comprise determining a first dissatisfaction function comprising a sum of an inconvenience function and a frustration function. The method may comprise determining the inconvenience function. The provisional path may include a direction from said current location to said intended destination and the profile includes a preferred step length, and wherein the determining of the inconvenience function and may include determining a first amount of work required to take a step of given step length and determining a second amount of work which is a proportion of said first amount of work corresponding to a component which is not directed in said optimal direction. The determining of the inconvenience function may include determining an acceleration associated with a change in velocity between said step and a previous step and determining a third amount of work required to produce said acceleration. The determining of the inconvenience function may include summing said second and third amounts of work. The method may include determining the frustration function. The profile may include a preferred walking speed and the determining of the frustration function may comprise determining a preferred instantaneous walking speed by adding said preferred walking speed to a value of walking speed noise and determining a fourth amount of work dependent upon a difference between the walking speed and the preferred instantaneous walking speed. The determining of the preferred step may comprise minimising said first dissatisfaction in respect of step length, minimising said first dissatisfaction in respect of step orientation thereby to obtain a preferred step length and a preferred step orientation. The determining whether said preferred step is feasible may comprise determining whether there is any discomfort arising from the entity having to keep a distance which is different from a preferred distance from an obstruction. The method may comprise determining if there is discomfort arising from the entity having to keep a distance which is different from a preferred distance from an obstruction.

[0022] The method may comprise providing a preferred clearance tolerance for said entity, and determining a personal space around said entity in dependence upon said clearance tolerance. The method may comprise determining a density of neighbouring entities and determining said personal space around said entity in dependence upon said clearance tolerance and said density of neighbouring entities. The method may comprise providing information relating to velocity of said entity; and determining an angular dependency for said personal space in dependence upon said velocity. The considering whether obstructions infringe said personal space may comprise determining whether said personal space is infringed at a first position along said preferred step and determining whether said personal space is infringed at a second position along said preferred step. The considering whether obstructions infringe said personal space may further comprise determining whether said personal space is infringed at a third position along said preferred step. If the preferred step is not feasible, then the method may further comprise determining a region in which to seek a compromise step. The determining of said region may comprise determining an arc and may include determining upper and lower angular limits and determining a radius of said arc.

[0023] The method may comprise determining a set of attributes for said autonomous entity in dependence upon said profile. The determining of said set of attributes may comprise determining at least one attribute at time of generating said entity.

[0024] The method may comprise modifying at least one attribute of said set of attributes for said autonomous entity.

[0025] According to the present invention there is provided a computer program for performing the method.

[0026] According to the present invention there is also provided a computer-readable medium storing the computer program.

[0027] According to the present invention there is also provided apparatus for simulating movement of an autonomous entity through an environment, the apparatus comprising an interface for providing a provisional path through a model of the environment from a current location to an intended destination, an interface for providing a profile for said autonomous entity, a processor for determining a preferred step towards said intended destination based upon said profile and said provisional path, a processor for determining a personal space around said autonomous entity, a processor for determining whether said preferred step is feasible by considering whether obstructions infringe said personal space.

[0028] According to the present invention there is also provided a method of simulating movement of an autonomous entity through an environment, the method comprising providing a preferred clearance tolerance for said entity and determining a personal space around said entity in dependence upon said clearance tolerance. The personal space may be anisotropic.

[0029] The method may comprise determining a density of neighbouring entities and determining said personal space around said entity in dependence upon said clearance tolerance said density of neighbouring entities. The method may comprise providing information relating to velocity of said entity and determining an angular dependency for said personal space in dependence upon said velocity.

[0030] According to the present invention there is also provided a method of designing a building structure, the method comprising providing a model of said building structure, simulating movement of at least one entity through said building structure, the simulating of said movement of said at least one entity comprises providing a provisional path through a model of the environment from a current location to an intended destination, providing a profile for said autonomous entity, determining a preferred step towards said intended destination based upon said profile and said provisional path, determining a personal space around said autonomous entity and determining whether said preferred step is feasible by considering whether obstructions infringe said personal space and revising said model of said building structure in dependence upon movement of said at least one entity. The building structure may be a building, such as a house, office block or railway station, an outside space for people, such as a sports stadium, or a mixture of both. The building structure may be a portion of a building or a portion of an outside space. The building structure may be passenger ship or aircraft. The building structure may be an open structure which is marked, for example with arrows and lines.

[0031] According to the present invention there is also provided a method of controlling movement of an entity through an environment, the method comprising providing a provisional path through a model of the environment from a current location to an intended destination, providing a profile for said autonomous entity, determining a preferred step towards said intended destination based upon said profile and said provisional path, determining a personal space around said autonomous entity, determining whether said preferred step is feasible by considering whether obstructions infringe said personal space.

[0072] A method of simulating movement of an autonomous entity through an environment according to the present invention is described which is suitable for use modelling pedestrian crowd movement. Thus, in this context, the terms “agent”, “entity” and “pedestrian” may be used interchangeably.

Motion of a Pedestrian

[0073] Navigating from a current position to an intended destination may be considered as involving two aspects, namely long-range, quasi-static navigation and short-range, dynamic navigation. These are hereinafter referred to as “macro-navigation” and “micro-navigation” respectively.

Navigation: Macro-Navigation

[0074] Referring to FIG. 1, a vacant venue 1 is shown as an architectural plan of the geometry and positions of walls 2, corridors 3 and fixed obstacles 4.

[0075] The walls 2, corridors 3 and fixed obstacles 4 do not change position over time and so they constitute static attributes of the environment. Static features may also include slow-moving obstacles, which are stationary over a timescale of approximately one step, i.e. quasi-static obstacles. For example, a stationary group of people may be treated as a fixed obstacle. Static features may also include moveable obstacles that are temporarily stationary, such as a barrier or door. Static information is employed to define a compass to indicate an apparent general direction en route to the ultimate destination.

[0076] A pedestrian 5 standing at a current location 6, in this case an entrance to the venue, usually aims himself or herself at an intended destination 7, such as an exit, by virtue of being familiar with the venue or by consulting a map or sign. In doing so, the pedestrian 5 selects a general direction of travel, which is called the “original direction”. The original direction may be maintained if the intended destination 7 is directly accessible from the current location 6. Alternatively, the original direction may be successively updated whenever an intermediate landmark 8₁, 8₂, 8₃ is reached, for example when an ultimate destination 9 is invisible or inaccessible from the current location 6. Thus, progress to an ultimate destination 9 comprises updating the pedestrian's current location 6 and, when an intermediate intended destination 7 is reached, setting a new intermediate intended destination, for example fixed on a new landmark 8₁, 8₂, 8₃.

[0077] The process of selecting a general direction on the basis of long-range quasi-static information, such as the geometry of a venue and the presence of large fixed obstacles, is referred to as “macro-navigation”.

[0078] Macro-navigation supplies a sequence of such intended intermediate destinations, starting from an entrance to ending at an exit or other final destination. The sequence may be supplied all at once, on entry to the venue, or one at a time, dynamically en route. Macro-navigation supplies an orientation angle {circumflex over (θ)}_o to a current intermediate intended destination from any point accessible from within the interior of a venue and at all times.

[0079] Macro-navigation may be “hard-wired”, implemented heuristically or using a sophisticated algorithm. For example, if macro-navigation is “hard-wired”, a venue is divided into zones and an intended orientation is provided for each zone. An example using zones is described later.

[0080] In an embodiment of the present invention, a rough approximation of an optimal path 9 is determined using a spatial objective, i.e. the ultimate intended destination, in conjunction with the geometry of the venue 1. The rough approximation of the optimal path serves as a compass indicating an intended orientation. The rough approximation of the optimal path 9 is also referred to as a provisional path.

[0081] For example, an optimal path 9 in relation to the geometry of the venue may be considered as a sequence of straight line segments taking the pedestrian from an entry point, around corners and obstacles, through intermediate intended destinations 7 or decision points, to the a final destination.

[0082] Thus, macro-navigation supplies an optimal path to a lowest order on the basis of a pedestrian's current position, intended destination and any static or quasi-static elements of the geometry of a venue. Macro-navigation does not take into account any preferences and attributes of each individual or dynamical considerations and is, therefore, subject to adjustments and corrections.

Navigation: Micro-Navigation

[0083] Referring to FIG. 2, the vacant venue 1 is now filled with other pedestrians 10 and is subject to dynamic events.

[0084] A busy railway station, for example, may include large numbers of arriving and departing pedestrians which are moving in different directions, waiting or queuing. Planned events may occur, such as scheduled arrivals and departures of trains. Also, chance events, for example arrival of delayed trains, may occur.

[0085] The pedestrian 5 needs to modify its route to avoid other pedestrians 10 and the process of adjusting and correcting for short-range, dynamic interactions is referred to as “micro-navigation”. This results in a modified route 9′. This is described in more detail later.

Discretisation

[0086] Referring to FIG. 3, a simplified plan view of the pedestrian 5 is shown.

[0087] The pedestrian 5 advances in whole steps 11, each of duration Δt. Thus, if a previous step j−1 began at time t_j−1, then the previous step ends and a current step j starts at t_j=t_j−1+Δt. Similarly, the current step ends and a subsequent step begins at t_j+1=t_j+Δt.

[0088] Walking is a complicated process. Therefore, the process is simplified by making some assumptions.

[0089] The effect of pedestrian “zigzagging” may be eliminated or reduced by choosing the centre of the pedestrian's head 12 to represent the position 13 of the pedestrian. This is because the pedestrian's head 12 lies, on average, approximately half way between the two feet in two successive steps. Any residual zigzagging between steps is attributable to spurious noise or intentional changes of direction.

[0090] Variations in the walking speed may be assumed to be exclusively due to variations in the step length rather than variations in the step duration

[0091] Walking is a non-linear process. Each foot is successively raised, then placed in contact with the ground so as to apply traction for locomotion. Over the course of any one step non-constant forces are exerted that result in irregular acceleration patterns and complicated speed dependencies. Nevertheless, uniform acceleration is assumed. This is a reasonable assumption provided that the duration of a step Δt is kept small. In this case, the duration of a step for an adult is set as 600 ms, i.e. Δt=0.6 s.

[0092] Thus, the pedestrian 5 may be described in terms of three independent variables, namely:

[0093] $\begin{array}{cc}{\stackrel{\_}{r}}_{j-1{,}_{t}j+1}{\stackrel{\_}{v}}_j=\frac{{\stackrel{\_}{r}}_{j+1}-{\stackrel{\_}{r}}_i}{\Delta t}{\stackrel{\_}{a}}_j=\frac{{\stackrel{\_}{v}}_i-{\stackrel{\_}{v}}_{i-1}}{\Delta t}=\frac{{\stackrel{\_}{r}}_{i+1}-2{\stackrel{\_}{r}}_j+{\stackrel{\_}{r}}_{j-1}}{\Delta t^2}& \left(1a,1b,1c\right)\end{array}$
where {right arrow over (r)} is position, {right arrow over (v)} is velocity, {right arrow over (a)} is acceleration and t is time.

[0094] Thus, a series or sequence of steps, represented byline segments 11 each of duration Δt, form the path 9.

Preferred Speed

[0095] An unhurried pedestrian walking on a level surface without any obstacles in sight has a preferred walking speed v₀. Preferred walking speed may also be known as “natural walking gait”.

[0096] Values of preferred speed may be experimentally determined for different populations in different circumstances, such as different venues, surfaces, inclines etc.

[0097] There is a linear relationship between speed v and step length l. Thus, variations in pedestrian speed for fixed step duration may be attributed to variations in step length. Therefore, a preferred step length l₀ may be defined as:
l₀=v₀Δt  (2)

[0098] Step length l₀ may also be expressed as half a stride interval.

[0099] A value of preferred speed is randomly drawn from a preferred speed continuous probability distribution. This usually occurs only once per entity when the entity is generated. However, further value of preferred speed may be drawn or existing values modified according to changes in environment.

[0100] The preferred speed continuous probability distribution is included in a profile and is derived from a statistical analysis of measured values of preferred walking speed for a large number of pedestrians over many steps. A profile includes one or more continuous distribution functions for one or more corresponding attributes, such as preferred speed, which characterise a particular type or “species” of pedestrian.

[0101] To a lowest order, step length variability may be approximated by noise or spontaneous random fluctuations. Thus, fluctuations in the step length may be represented as fluctuations in preferred speed. Experiments may be used to measure these variations and thus determine probability distributions.

[0102] Thus, a spontaneous preferred-speed noise may be defined as:
δv₀=α_nΔt  (3)
where α_n is a spontaneous value of acceleration.

[0103] A value of δv₀ (or α_n) is drawn from a spontaneous preferred-speed probability distribution also comprised in the profile. However, unlike preferred speed, a value of spontaneous preferred-speed noise is usually drawn once per entity per step.

Micro-Navigation

[0104] A macro-navigation module supplies a provisional path for taking a pedestrian from an entry point through a venue to his final destination. The provisional path is corrected and adjusted to account for individual pedestrian preferences.

[0105] As explained earlier, at each point in time a pedestrian need only know the next intermediate destination point, such as a corner or obstacle, and not necessarily the final destination which may only be determinable at a later decision point. It does not matter whether the full optimal path is available from the outset or only the current leg leading up to the next intermediate destination. Once the lowest-order optimal path is available, at least up to the next intermediate destination or decision point, pedestrians or entities invoke micro-navigation.

[0106] The micro-navigation process seeks to supply criteria, decision making powers, learning and adaptation faculties that permit an entity to read signals from its surroundings, process these together with the lowest-order optimal path and the knowledge of one's own preferences and attributes so as to deduce a truly optimal path. It also seeks to learn and update memory with up-to-the-moment information, project the intentions of neighbouring entities and negotiate with them and ultimately execute one step so as to stay nearest the true optimal path while at the same time suffering the least harm or degrading in regard to the pedestrians own well-being.

[0107] Every optimal step leading to the final destination belongs to the optimal path. Thus, if a pedestrian has their way, as for example in the empty railway station, the process of achieving the ultimate destination would be accomplished by simply following the optimal path, one step at a time, at the pedestrian's preferred speed.

[0108] However, the presence of obstacles and/or other entities and impeding external factors beyond one's control, usually render the optimal step non-viable. Thus, a compromise needs to be made. Micro-navigation is concerned with this situation and includes three stages:

[0109] In a first stage, the method comprises receiving the provisional path and the entity's preferences and attributes and determining a preferred step. The result of the first stage is a preferred position for the next step.

[0110] In a second stage, the method comprises determining a personal space around said entity and determining whether the preferred step is feasible. This comprises determining whether personal space around the entity is infringed by another entity or obstacle at any point during the preferred step. This includes determining whether a projected path of the other entity infringes the entity's personal space. As will be explained in more detail later, personal space is anisotropic and may depend on a number of factors including the velocity of the entity and apparent velocity of neighboring entities.

[0111] If the preferred step is not feasible, the method includes determining a region in which to seek a compromise step. The result of the second stage is an area in proximity to the preferred position in which an alternative position is sought. Another result is knowledge of the local conditions which will facilitate more prudent decision making in the future, as well as adjustment of the entity's own preferences, such as its preferred speed and size of its personal space.

[0112] In a third stage, the method comprises determining whether at least one compromise step is feasible within the specified region. As will be explained in more detail, this process comprises minimising a function referred to as “full dissatisfaction” and seeking compromise steps from the least dissatisfying to the most dissatisfying. Any solution constitutes a compromise in that the entity no longer seeks to satisfy his or her original preferences (as in the first stage), but rather strives for degraded, adjusted preferences obtained by the end of the second stage. It may include eliminating candidate solutions due to unavailability, after negotiating with neighbours by cooperating or competing, and evading fixed obstacles. The result of the third stage is a solution for a compromise step. Thereafter, the step may be taken.

[0113] This process is iterated, one step at a time, for each entity until it reaches its destination.

Micro-Navigation: Stage I

[0114] Referring to FIG. 4, the pedestrian completes a step 11₁ from a previous position 12₁ to a current position 12₂, i.e. from (x_j−1, y_j−1) to (x_j, y_j), and is about to embark on his next step 11₂.

[0115] The pedestrian's objective is to reach intended destination 7, i.e. at target coordinates (x_t, y_t). To achieve this, an orientation angle {circumflex over (θ)}₀^j is provided corresponding to the lowest-order optimal path.

[0116] In effect, the pedestrian uses this orientation angle {circumflex over (θ)}₀^j as a rough compass. However, to determine a truly optimal next step, the pedestrian's preferences are taken into account.

[0117] To achieve this, a first Action function J_S is determined and minimised. This is executed without considering any external impediments. The first Action function J_S is herein referred to as “self-dissatisfaction”. As will be explained later, another Action functional J_T is determined during later stages of micro-navigation which includes external impediments and is referred to as “full dissatisfaction” or simply “dissatisfaction”.

[0118] The pedestrian may take the next step 11₂ and move to a new position 12₃ within a dashed circle 14. There are two degrees of freedom represented by two independent variables, namely length l and direction angle θ of the next step. Polar coordinates (l,θ) are used instead of Cartesian coordinates (x,y) as a matter of convenience.

[0119] If the pedestrian considers step 11₂ as a candidate for the next step to a virtual position 12₃ at (x_j+1, y_j+1), then he or she expends work against friction-like forces in traversing the path, namely:
W_f^j=μgml_j  (4)
where g is gravitational acceleration, m is the mass of the individual pedestrian, μ is a coefficient of friction and l_j is the length of the step actually traversed over time step j. The coefficient of friction induces the work against friction to be proportional to the softness or hardness between the two surfaces of contact, namely the pedestrian's shoes and the floor. A coarse floor results in a larger value of μ, while a polished floor results in a smaller value.

[0120] Here, “friction” is taken to encompass all possible friction-like forces depending on the path length and the mass of the moving object. Therefore, μ can be considered more generally as a “coefficient of difficulty”. Thus, not only is traversing a coarse floor energetically more costly than traversing a polished floor, i.e. “standard” friction, but also traversing an inclined floor, as opposed to a level floor, will be energetically more expensive. The coefficient is a spatial attribute which can be established empirically by analysing behaviour of pedestrians on different types of floors.

[0121] If the pedestrian picks step 11₂ as the next step, then he or she would end up moving in a direction different from his apparent present intended orientation {circumflex over (θ)}₀^j. Working against friction so as to move the pedestrian toward the intended destination 7 is acceptable, but not otherwise. Thus, a component 15 of the path corresponding to the step 11₂ along the intended direction {circumflex over (θ)}₀^j, amounts to the useful path. A component ΔW_f^j corresponds to wasteful work, namely:
ΔW_f^j=μmgl_j[1−cos (θ_j−θ₀^j)]  (5)

[0122] Thus, ΔW_f^j may be interpreted as one component of perceived inconvenience due to wasteful work against friction induced by deviating from the intended direction over the course of one step.

[0123] The previous and current steps 11₁, 11₂ may differ in both length l and angle θ. These changes are caused by a force and result in acceleration. For example, a force exerted parallel to the direction of travel may cause acceleration which results in l_j>l_j−1, or conversely deceleration which results in l_j<l_j−1. A force exerted perpendicular to the direction of travel results in a change of direction from θ_j−1 to θ_j. Thus, equation 1c and 5 may be written as:

[0124] $\begin{array}{cc}{\stackrel{\_}{a}}_j=\frac{1}{\Delta t^2}\left\{\left(l,\cos {\theta }_j-l_{j-1}\cos {\theta }_{j-1}\right)\stackrel{̑}{x}+\left(l_j\sin {\theta }_j-l_{j-1}\sin {\theta }_{j-1}\right)\stackrel{̑}{y}\right\}& \left(6\right)\\ \Delta W_a^j=\int {\stackrel{\_}{F}}_j·d{\stackrel{\_}{s}}_{j·j^{-1}}=m{\stackrel{\_}{a}}_j^2{\int }_0^{\Delta t}tdt=\frac{m}{2\Delta t^2}\left[l_j^2-2l_j{l}_{i-1}\cos \left({\theta }_j-{\theta }_{j-1}\right)+l_{i=1}^2\right]& \left(7\right)\end{array}$

[0125] The work ΔW_a^j exerted during step j to produce acceleration {right arrow over (a)}_j may be considered as a second component of inconvenience.

[0126] Thus, a total inconvenience, I, associated with perceptions of wasteful effort over the course of a step may be defined as:
I(l,θ)=≡c_i(ΔW_f^j+ΔW_a^j)  (8)
where coefficient c_i is a context-dependent scaling factor. The scaling factor may be determined by fitting a model to measured data.

[0127] So far, the expended work associated with inconvenience may be thought as physical work in a traditional classical mechanical sense.

[0128] However, “work” can also be expended in other ways, as we shall now explain.

[0129] As we explained earlier, the entity has a velocity that fluctuates about a preferred speed v₀ which is an individual attribute of each entity and subject to spontaneous fluctuations δv_j⁰, namely:
v_j⁰=v₀+δv_j⁰  (9)
where v₀ is the preferred cruising speed and δv_j⁰ is the spontaneous speed noise for step j. A value of v₀ is assigned to each entity and is drawn from a preferred speed distribution function. A value of δv_j⁰ is randomly drawn from a corresponding spontaneous speed noise distribution function for each entity for each step. Thus, v_j⁰ is an instantaneous preferred speed of an individual pedestrian over step j.

[0130] A preferred speed, which is self-imposed, is tantamount to a constraint. Thus, it may be classified as an effective potential energy term, as can be shown by invoking variational techniques. Here, a quadratic energy term is assigned:

[0131] $\begin{array}{cc}{F}_j\left(l\right)=c_f\frac{1}{2}{m\left(\frac{l_j}{\Delta t}-{\upsilon }_j^0\right)}^2& \left(10\right)\end{array}$
which has a potential minimum when l_j=v_j⁰Δt, i.e. when the length of the step results in an instantaneous speed equal to the preferred cruising speed.

[0132] F_j is referred to as “frustration” and considered as virtual, rather than physical, work. It reflects the cost due to differences between the actual instantaneous speed l_j/Δt and the desired speed v_j⁰.

[0133] Referring to FIG. 5, a plot of frustration against instantaneous speed is shown, wherein v_j⁰=1.3 ms⁻¹, c_f=1N⁻¹ per unit mass.

[0134] The sum of inconvenience and frustration is hereby defined as “self-dissatisfaction”, i.e.:
J_S(l,θ)≡I(l,θ)+F(l)  (11)

[0135] FIGS. 6a and 6b show two- and three-dimensional plots of self-dissatisfaction for initial values l_j−1=1.0 m and θ_j−1=50° and current preferences of θ_j^o=90° and v_j^o=1.3 ms⁻¹.

[0136] Self-dissatisfaction is the perceived undesirable cost contrary to physical and physiological traits. It is self-referential and does not take account of external factors.

[0137] In this example, equation 11 is derived using the Lagrangian formalism. Following an approach based on variational techniques, equations of motion can be obtained by determining the stationary point of Action by minimizing J_S(l,θ) or solving the system of differential equations, namely:

[0138] $\begin{array}{cc}\frac{d}{dl}\Delta J_S\left(l,\theta \right)=0& \left(12\right)\\ \frac{d}{d\theta }\Delta J_S\left(l,\theta \right)=0& \left(13\right)\end{array}$

[0139] The equations of motion may also be obtained by invoking ad-hoc phenomelogical forces which lead to an analogous result.

[0140] The solution yields the optimal next step, namely:

[0141] $\begin{array}{cc}{\theta }_j^{\mathrm{opt}}=\arctan \left[\frac{l_{j-1}\sin {\theta }_{j-1}+\mu g\Delta t^2\sin {\theta }_j^0}{l_{j-1}\cos {\theta }_{j-1}+\mu g\Delta t^2\cos {\theta }_j^0}\right]& \left(14,15\right)\\ \begin{array}{c}{l}_{\mathrm{opt}}\left({\theta }_j\right)=\frac{1}{c_i+c_f}[c_f{v}_j^0\Delta t-c_i\mu g\Delta t^2\left(1-\cos \left({\theta }_j-{\theta }_j^0\right)\right)+\\ c_i{l}_{j-1}\cos \left({\theta }_j-{\theta }_{j-1}\right)]\end{array}& \end{array}$

[0142] Equation 14 supplies a single value for the optimal orientation angle

[0143] ${\theta }_j^{\mathrm{opt}}.$
Equation 15 expresses the step length as a function of orientation angle. In particular, for any chosen direction θ_j the optimal path for that angle is given by l_opt(θ_j). The optimal step length is obtained by replacing θ_j by

[0144] ${\theta }_j^{\mathrm{opt}},$
so that the set

[0145] $\left({\theta }_j^{\mathrm{opt}},l_{\mathrm{opt}}\left({\theta }_j^{\mathrm{opt}}\right)\right)$
describes the optimal step. The optimal orientation angle

[0146] ${\theta }_j^{\mathrm{opt}}$
and optimal step length l_opt specify the step which the pedestrian would like to take. Thus, they are referred to as the “preferred orientation angle” and “preferred step length” respectively.

[0147] The values of

[0148] $\left({\theta }_j^{\mathrm{opt}},l_{\mathrm{opt}}\left({\theta }_j^{\mathrm{opt}}\right)\right)$
are used in the next stage of micro-navigation.
Pedestrian Interactions

[0149] The preferred step described by the set of values

[0150] $\left({\theta }_j^{\mathrm{opt}},l_{\mathrm{opt}}\left({\theta }_j^{\mathrm{opt}}\right)\right)$
is achievable in the absence of environmental impediments such as fixed obstacles or other pedestrians which may otherwise prohibit it from being taken. In practice, however, the preferred step usually cannot be taken. This may be because the pedestrian is in a densely populated area or due to fixed obstacles.

[0151] As will be described in more detail later, the preferred step is not taken if any point along its length is associated with a non-vanishing value of a function referred to as “discomfort”. Discomfort arises as a result of infringement of a subjectively determined area known as personal space.

[0152] If the preferred step cannot be taken, then a search is made for an acceptable, feasible compromise step.

[0153] Potentially, a search space lies within a circle centred on the pedestrian's current location and having a radius equal to the maximum distance possible over the course of one step. However, it is unusual for a pedestrian to consider taking a step backwards when avoiding other pedestrians and obstacles. Similarly, it is rare that the pedestrian will come to a complete stand still or run at full speed. Thus, many potentially feasible next steps can be immediately eliminated. Thus, acceptable compromise steps are picked from narrower range of angles and step lengths.

[0154] The second stage of micro-navigation comprises establishing criteria for deciding which subset of feasible next steps is worth looking into and applying these criteria to restrict the domain of acceptable solutions from a full circle to a narrow subspace with fixed angular and step-length boundaries.

[0155] A second Action function J_T called “dissatisfaction” is used which considers discomfort arising when neighbouring pedestrians and fixed obstacles infringe an entity's personal space.

[0156] The interaction of the pedestrian with their surroundings may be considered as competition for space. The pedestrian, by virtue of being a physical object, occupies physical space. At the very least, the area physically available must be sufficient to accommodate the pedestrian's physical space. However, there are also psychological spatial requirements. Pedestrians require personal space, or clearance from their nearest neighbours and obstacles in order to feel comfortable. In dealing with pedestrian interactions, account is taken of both the physical and psychological requirements for personal space. To achieve this additional attributes and preferences for pedestrians are used.

[0157] Pedestrians are assigned a set of characteristics including intrinsic attributes, such as physical space requirements, and preferences, such as preferred speed. These characteristics are included in a profile.

[0158] As explained earlier, a profile includes one or more continuous distribution functions for one or more corresponding attributes, such as preferred speed, which characterise a particular type or “species” of pedestrian. Each continuous distribution function describes empirically established attributes of real population samples which have been measured and analysed.

[0159] Core profiles may include pedestrian attributes based on fundamental criteria such as ethnicity, which may represent physical and cultural differences, venue, which represent contextual differences such as behaviour in a railway station as opposed to a stadium, and sex, which reflect physical differences such as physical space occupied or speed. The assignment of a core profile to an entity is a one-off event, for example when generating an entity in a simulation and subsequently remains the same. Some attributes, such as preferred walking speed are drawn only once when the entity is generated. Other attributes may be repeatedly, randomly drawn, for example every step. Attributes described in core profiles are referred to as “intrinsic” attributes.

[0160] Secondary or transient features may also be used. These may include physical space occupied due to the carrying of luggage. These attributes can be assigned to the entity at the same time as the core feature, although they may change one or more times.

[0161] One aspect of the second Action function J_T, is the introduction of an additional term referred to as “discomfort” which accounts for the perceived reduction of desired personal space due to external impediments. Thus, a spatial area is defined having a specific form and size which the pedestrian attempt to keep clear of fixed obstacles and neighbouring pedestrians. Another aspect is that it may use modified entity attributes, as for example a modified preferred speed adjusted for local circumstances, rather than the value originally drawn from its profile.

Physical Size of a Pedestrian

[0162] Referring to FIG. 7, a physical form or area 16 that a pedestrian occupies may be approximated by an ellipse. The ellipse 16 is defined in terms of its major and minor axes a, b, which are referred to here as “shoulder breadth” and “body depth” respectively.

[0163] Reference is made to “Bodyspace Anthropometry, Ergonomics and the Design of Work” by Stephen Pheasant (2^nd Edition, Taylor and Francis, London 1998) which describes numerous population samples selected by ethnicity, sex and age groups.

[0164] The major and minor axis parameters are drawn from as Gaussian (or normal) distribution or other suitable curves. For a Gaussian representation, four parameters are used to represent each population sample, namely a centroid and a standard deviation of the Gaussian probability distribution curve for each ellipse axis.

[0165] Assigning a physical size to an entity is equivalent to attributing suitable values for the shoulder breadth and body depth axes of the ellipse. However, a simpler form can be used, such as a circle, which requires a single parameter, namely radius, and which easier to manipulate due to its symmetry. This is useful when considering overlap between the pedestrian and other pedestrians and obstacles.

[0166] The ratio of major to minor axis is near constant per population sample for the mean, lower (5%) and higher end (95%) of the Gaussian probability distributions supplied. For example, for British men the ratio (b/a) is close to 0.637, wherein a is the shoulder breadth (major axis) and b the body depth (minor axis). Thus, sampling one parameter from its proper distribution function, say the shoulder breadth, the other parameter may be determined by the ratio above.

[0167] Whereas the net area of the physical space is important, it appears that there is no sensitivity in the form between an ellipse and a circle of equal area. For densities up to about 9.5 persons per square meter (ppsm), which are extremely high and rare, pedestrians maintain a personal space around them that is larger than their physical space. While this is the case, the area of the physical space is entirely contained within the personal space, i.e. psychological considerations take precedence over physical constraints. Under those circumstances the form of physical space is not important so long as the area is preserved and replacing the elliptical form by a circular one has no noticeable quantitative effect. For extremely high densities, again the net area is more important.

[0168] Referring to FIG. 8, the physical space occupied by a pedestrian may be approximated by a circle 17 of radius R₀, namely:

[0169] $\begin{array}{cc}\pi \frac{\mathrm{ab}}{4}\approx \pi \langle b/a\rangle \frac{a^2}{4}=\pi R_0^2\Rightarrow R_0=\sqrt{\langle b/a\rangle }\frac{a}{2}& \left(16\right)\end{array}$
and <b/a> is the mean value of the ratio of the two axes per population sample. The radius is derived by setting the area of the ellipse equal to the area of the circle.

[0170] In summary, population samples selected by ethnicity, sex, age group and other criteria can be described using a Gaussian probability distribution of shoulder breadth and a mean ratio of shoulder breadth to body depth from empirical measurements.

Physical Size of Luggage-Carrying Pedestrians

[0171] A frequently encountered transient attribute is the increase in physical size due to the carrying of luggage.

[0172] Referring to FIG. 9, an increase in size due to carrying luggage can be absorbed into an extended circle 18 with area equal to the sum of the original entity area 17 and that of the luggage 19.

[0173] Thus, if R_o is the entity radius and a′, b′ are the length and width respectively of a piece of luggage, then the areas occupied by the entity and the luggage are A=πR_o² and a=a′b′ respectively. Thus, the effective area is calculated as:
A′=A+α  (17)
and the effective entity radius is determined to be:
R_o′=√{square root over (A′/π)}  (18)

[0174] Referring to FIG. 10, Gaussian distribution functions 20₁, 20₂, 20₃, 20₄ for assorted, small, medium and large luggage are shown. For example, for small luggage, a mean area may be 0.3 m×0.2 m=0.06 m². For medium and large luggage, mean areas may be 0.7 m×0.3 m=0.21 m² and 1.0 m×0.4 m=0.04 m² respectively. The Gaussian distribution functions 20₁, 20₂, 20₃, 20₄ are used to assign luggage sizes randomly to designated entities.

Personal Space in Pedestrian Behaviour

[0175] Personal space is the area a pedestrian strives to maintain clear of obstacles and other pedestrians while walking or standing.

[0176] Referring to FIG. 11, the pedestrian 5 at current location 12₂ is evaluating position 12₃ as candidate for their next step. The pedestrian 5 is also estimating the personal space that will be available at that position 12₃ given that a neighbouring pedestrian 21 may also be competing with them for the space. Other neighbouring pedestrians may also be competing for the space and may also be included. Nevertheless, for the sake of clarity, only one neighbouring pedestrian is shown.

[0177] The neighbouring pedestrian 21 previously took a step 22₁ from a first position 23₁ to their current position 23₂ at time j−1 and, from the point of view of the pedestrian 5, appears to be considering taking a step 22₂ to a new position 23₃ at time j.

[0178] The pedestrian 5 estimates the future position of neighbouring pedestrian 21. The true intention of the neighbouring pedestrian is unknown and so any prediction is based on observations. This prediction is based on an apparent speed and direction of the neighbouring pedestrian 21, namely those of their most recently completed step 22₁.

[0179] The situation may be described by the following set of equations:

[0180] $\begin{array}{cc}{\stackrel{\rightharpoonup }{r}}_j^{i,k}=x_j^{i,k}\hat{x}+y_j^{i,k}\hat{y}& \left(19,20,21,22,23,24\right)\\ {\stackrel{\rightharpoonup }{r}}_{j+1}^i=x_{j+1}^i\hat{x}+y_{j+1}^i\hat{y}& \\ \delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^i=l_j^k{\hat{\theta }}_j^i& \\ \delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^k=l_{j-1}^k{\hat{\theta }}_{j-1}^k& \\ {\stackrel{\rightharpoonup }{r}}_{j+1}^k={\stackrel{\rightharpoonup }{r}}_j^k+\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^k& \\ \delta {\theta }_j^{i,k}={\cos }^{-1}\left(\frac{\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^i·\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^k}{\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^i\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^k}\right)& \end{array}$
where

[0181] ${\stackrel{\_}{r}}_j^{i,k}$
is the current position of the pedestrian 5 and neighbouring pedestrian 21 respectively, {right arrow over (r)}_j+1ⁱ is the targeted position 12₃′ of the pedestrian 5,

[0182] $\delta {\stackrel{\_}{r}}_{j,j+1}^i$
is the change in position of the pedestrian 5 over step j,

[0183] $\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^k$
is the projected change of position of the neighbouring pedestrian 21 over step j,

[0184] ${\ddot{r}}_{j+1}^k$
is the projected position 23₃′ of the neighbouring pedestrian 21 after step j and δθ_j^i,k is a relative angle between the step 11₂ and apparent step 22₂.

[0185] In defining personal space, several considerations may be taken into account:

[0186] As described earlier, the clearance sought from surrounding neighbours depends on the position and velocity of both the individual and the surrounding neighbours. The positions of surrounding neighbours are projected by processing available information and prognosticating intentions, i.e. assuming that they will continue to be moving in the same direction and with the same speed over their next step as they were last observed to have in their most recently completed step.

[0187] The angular dependence of desired clearance is correlated with speed. In particular, personal space is distributed uniformly while standing, whereas it is increased in favour of the forward direction when moving forward. Thus, the shape and size of personal space is dynamically adjusted as a function of the pedestrian's motion relative to their surrounding neighbouring pedestrians and obstacles.

[0188] The personal space also depends on density. In densely packed crowds individuals tend to relax their requirements and accept less space than they would have under less constrained circumstances. This is a form of adaptation by habituation, which is described in more detail later.

[0189] Differentiations in preferences for personal space across species or different population samples selected, for example by ethnicity or context, also exist. The origin of these may be either physical, cultural, or contextual, also exist. Furthermore, even within a uniform population sample or species, individuals range in their needs for personal space.

[0190] Variations in needs for personal space are described in terms of a “rank”. Entities are classified by their rank within their own population. A number between 0 and 1 may be used to indicate the proportion of the population which is more tolerant with regard to requirements of clearance for personal space. Thus, an entity may draw a mean personal space rank S_i⁰.

[0191] There are spontaneous variations, or noise, in the individual personal space preferences of pedestrians, similar to speed noise described earlier. Thus, an instantaneous personal space rank S_i^j may be defined as:
S_i^j=S_i⁰+δS_i^j  (25)
where S_i⁰ is the mean personal-space rank and δS_i^j is the instantaneous noise. S_i⁰ and δS_i^j are drawn randomly from probability distribution functions derived from fits to measurements.

[0192] Based on these considerations and using standard statistical analysis techniques and fits to empirical data, personal space

[0193] ${ℛ}_{j+1}^l$
may be defined as:

[0194] $\begin{array}{cc}{ℛ}_{j+1}^l\left(\theta \right)=\frac{S_i^j}{\sqrt{{\rho }_j^i}}\left[1+\frac{l_j^i}{\Delta t}\left(c_1\cos \theta +c_2\cos 2\theta \right)\right]& \left(26\right)\\ {ℛ}_{j+1}^{\mathrm{ik}}\equiv {ℛ}_{j+1}^{\mathrm{ik}}\left(\delta {\theta }_{j+1}^{i,k}\right)& \left(27\right)\end{array}$
where

[0195] ${ℛ}_{j+1}^{\mathrm{ik}}$
is the desired clearance of pedestrian 5 from neighbouring pedestrian 21 following step j as a function of its instantaneous personal-space rank S_i^j and the relative angle

[0196] ${\mathrm{\delta \theta }}_j^{i,k}$
between the pedestrians 5, 21. Parameters c₁, c₂ are derived from fitting the model to data, Δt is the duration of a step and ρ_jⁱ is the pedestrian density in units of pedestrians per square meter (ppsm), as experienced by the pedestrian 5 at time j.

[0197] In equation 26, personal space R_j+1ⁱ exhibits anisotropic angular dependence. Personal space is also a function of the entity's own speed l_jⁱ/Δt and local density ρ_jⁱ. The dependency of personal space on local density ρ_jⁱ is a manifestation of adaptation by habituation, which will be described n more detail later.

[0198] In equation 27,

[0199] $R_{j+1}^{ik}$
is defined with reference to neighboring pedestrians by a relative angle

[0200] $\delta {\theta }_{j+1}^{i,k}$
which takes account of the relative position and projected speed of the neighboring entity to the entity. It is individually calculated for each individual pedestrian at each time step.

[0201] Referring to FIG. 12, plots of personal space

[0202] ${ℛ}_{j+1}^i$
for a pedestrian for different speeds and having a rank equal to the mean obtained from fitting measured personal spaces is shown. First, second, third, fourth and fifth plots 24₁, 24₂, 24₂, 24₄, 24₅ are for a pedestrian at rest and moving at 0.5, 1.0, 1.5 and 2.0 ms⁻¹ respectively.

[0203] The virtual work corresponding to the perceived cost of being deprived of desired personal space is referred to as “discomfort”. An effective potential energy term is assigned similar to the potential energy of a compressed spring. Other forms of effective potential energy may also be assigned provided. The potential energy may vary linearly or non-linearly, logarithmically or exponentially or may include polynomial terms.

[0204] The preferred distance of a pedestrian from each of their neighbours is similar to a relaxation length of a spring. Being obliged to keep a shorter distance than the one preferred one is similar to compressing a spring which consequently acquires potential energy equal to the work needed to compress it.

[0205] Thus, discomfort is the sum of potential energy terms for each neighbour, namely:

[0206] $\begin{array}{cc}\Delta r_{j+1}^{ik}=R_{j+1}^{ik}-{\stackrel{\rightharpoonup }{r}}_{j+1}^i-{\stackrel{\rightharpoonup }{r}}_{j+1}^k& \left(28,29,30\right)\\ V_{j+1}^{ik}\equiv \frac{1}{2}{c_d\left(\Delta r_{j+1}^{ik}\right)}^2\Theta \left(\Delta r_{j+1}^{ik}\ge 0\right)& \\ D_{j+1}^{\mathrm{neighbors}}\equiv \sum _{k\in \left(\mathrm{neighbors}\right)}^{}{V}_{j+1}^{ik}& \end{array}$

[0207] $\Delta r_{j+1}^{ik}$
is the deficit between the desired clearance

[0208] $R_{j+1}^{ik}$
and the actual head-to-head distance

[0209] ${\stackrel{\rightharpoonup }{r}}_{j+1}^i-{\stackrel{\rightharpoonup }{r}}_{j+1}^k$
between the pedestrian 5 and an offending neighbour such as pedestrian 21.

[0210] $V_{j+1}^{ik}$
is the compression energy arising between the pedestrian 5 and an offending neighbour, such as pedestrian 21. The step Θ function ensures that neighbouring entities outside a pedestrian's personal-space do not contribute to discomfort since they are sufficiently far away. The parameter c_d is a strength parameter extracted from fits to data. The total discomfort

[0211] $D_{j+1}^{\mathrm{neighbors}}$
experienced by pedestrian 5 is the sum of all the ‘compression energy’ terms of all offending neighbours including neighbouring pedestrian 21. The parameter c_d is a strength parameter extracted from fits to data.

[0212] Discomfort arising from nearby fixed obstacles is treated similarly to discomfort arising from neighbouring pedestrians save for some minor adjustments.

[0213] Referring to FIG. 13, a pedestrian 5 is located at position 12₂ is considering taking the preferred step 11₂ to position 12₃.

[0214] Determining whether the preferred step 11₂ is feasible comprises determining whether another pedestrian 21 or obstacle 25 is found in their personal space 24. This is performed over the course of the step. Thus, the personal space 24 is moved along the track of the preferred step 11₂ and a search is conducted within the personal space 24 for other pedestrians 21 or obstacle 25. An instance of a shifted personal space 24′ is illustrated. The search may include determining whether another pedestrian 21, perceived to be taking a projected step 22₂, will move to a position 23₃ which is found in personal space 24.

[0215] Referring to FIG. 14, an obstacle 25 maintains a fixed position and may be represented by a sequence of segments 26, each segment having a beginning and end 27, 28. Discomfort is evaluated relative to the obstacle 25 by considering only portion 26₁ of segments infringing their personal space.

[0216] Thus, relations similar to equations 19, 20, 21, 22, 23, 24, 28, 29 and 30 may be derived in relation to a pedestrian 5 and a fixed obstacle 25, namely:

[0217] $\begin{array}{cc}{\mathrm{\delta \theta }}_j^{l,k}={\cos }^{-1}\left(\frac{\delta {\ddot{r}}_{jj+1}^i·{\tilde{L}}_k}{\delta {\stackrel{\_}{r}}_{jj+1}^iL_k}\right)& \left(31\right)\\ r_{j+1}^{\mathrm{ik},A,B}=\sqrt{{\left(x_{j+1}^i-x_{A,B}^k\right)}^2+{\left(y_{j+1}^i-y_{A,B}^k\right)}^2}& \left(32\right)\\ l_{A,B}^k=\frac{L_k^2\pm {\left(r_{j+1}^{\mathrm{ik},A}\right)}^2\mp {\left(r_{j+1}^{\mathrm{ik},B}\right)}^2}{2L}& \left(33\right)\\ {\varphi }_{j+1}^{\mathrm{ik},A,B}=\arcsin \left(\frac{l_{A,B}^k}{r_{j+1}^{\mathrm{ik},AB}}\right)& \left(34\right)\\ h_k=\sqrt{{\left(r_{j+1}^{\mathrm{ik},A,B}\right)}^2-{\left(l_{\mathrm{AB}}^k\right)}^2}& \left(35\right)\\ \Delta r_{j+1}^{\mathrm{ik}}={ℛ}_{j+1}^{\mathrm{ik}}-\frac{h_k}{\cos \varphi }& \left(36\right)\\ U_{j+1}^{\mathrm{ik}}\equiv \frac{1}{2}{c}_d^{\prime }{\int }_{{\varphi }_{j+1}^{\mathrm{ik},A}}^{{\varphi }_{j-1}^{\mathrm{ik},B}}d{\varphi \left(\Delta r_{j+1}^{\mathrm{ik}}\right)}^2\Theta \left(\Delta r_{j+1}^{\mathrm{ik}}\ge 0\right)& \left(37\right)\\ D_{j+1}^{\mathrm{obstacles}}\equiv \sum _{k\in \left(\mathrm{obstacles}\right)}{U}_{j+1}^{\mathrm{ik}}& \left(38\right)\end{array}$
where index k identifies the offending obstacle, where

[0218] $\delta {\theta }_j^{i,k}$
is the angle of path of pedestrian 5 and segment 26 over step j,

[0219] $r_{j+1}^{ik:A,B}$
is the distance between pedestrian 5 from beginning 27 and end 28,

[0220] $l_{A,B}^k$
is a portion of a segment portion 26₁,

[0221] ${\phi }_{j+1}^{ik:A,B}$
are angular limits, as seen from the entity's test position, corresponding to the beginning and end 27, 28 of the segment 26 of the obstacle that infringes personal space over step j, h_k is the distance of the pedestrian from segment 26,

[0222] $\Delta r_{j+1}^{ik}$
corresponds to the “height” of a triangle formed by the entity's current position and the end points 27, 28 of the segment 26 of the obstacle infringing personal space,

[0223] $U_{j+1}^{ik}$
is the compression energy of pedestrian 5 relative to obstacle 25 and

[0224] $D_{j+1}^{\mathrm{obstacles}}$
is the sum of discomforts due to obstacles experienced by pedestrian 5. The parameter c′_d is the entity-obstacle interaction strength extracted empirically from fitting to measurements. A cruder approximation of equation 37 may also be used.

[0225] Combining equations 30 and 38, the total discomfort is obtained namely:

[0226] $\begin{array}{cc}{D}_{j+1}^i=D_{j+1}^{\mathrm{neighbors}}+D_{j+1}^{\mathrm{obstacles}}& \left(39\right)\end{array}$
and a total dissatisfaction is also found, namely:

[0227] $\begin{array}{cc}\Delta J_{j+1}^{T_i}\equiv \Delta J_{i+1}^{S_i}+D_{j+1}^i& \left(40\right)\end{array}$
Micro-Navigation: Stage II

[0228] A pedestrian who is impeded by external factors, such as a neighbouring pedestrian or fixed obstacle, may be prevented from taking their preferred step. These external factors are perceived, processed and reconciled with the pedestrian's objectives and preferences. An ultimate decision regarding a least dissatisfying next step is one that better serves the pedestrian's interests.

[0229] The information on which this decision is based tends to be local, noisy and imperfect. The faculties that allow perceiving and processing information, learning, adapting and making a decision are characteristics of autonomous intelligent agents. These faculties lead to emergent behaviour known as self-organization.

[0230] The second stage of the micro-navigation includes establishing criteria and employing them to limit a search space for suitable next-step candidates. This principally involves finding suitable lower and upper angle bounds within which to seek the direction of the next step and adjusting the preferred speed, as required, to cope better with perceived local conditions.

[0231] To make a decision, the following considerations are taken into account, namely the unavailability of physical space due to the presence of neighbours and obstacles, the probability for competition with pedestrians in an apparent collision course and the necessity for cooperation with pedestrians in a similar course.

[0232] Thus, should the preferred next step be unavailable, a pedestrian can seek alternatives by reducing or increasing the length of their next step relative to their preferred length, additionally or alternatively by deviating left or right from their preferred orientation.

[0233] A first criterion is employed, namely the principle of habituation, which states that entities become accustomed to enduring certain dissatisfaction over time, commensurate with local conditions. They acquire a memory of dissatisfaction that serves as the yardstick for a rough first assessment of their well-being. Perceived compliance or advantage relative to the norm is reason to stay the intended course. A perceived deficit induces deviating, to seek improvement.

[0234] Thus, each entity establishes a norm of dissatisfaction, i.e. a subjective level that it deems acceptable on the basis of what is to be expected locally from previous experience. This norm is effectively a memory of past dissatisfaction levels over a number of previous steps with a rule for updating. Likewise, entities maintain a memory of actual step lengths, or equivalently walking speeds, over the same number of steps and updated by the same rule.

[0235] A simple rule for updating information is employed, which gradually phases out old information and incorporates new information at the end of each step.

[0236] After completing step j−1 and prior to launching a new search for step j, a dissatisfaction norm

[0237] ${\stackrel{\_}{\Delta J}}_j^{T:i}$
and a feasible step length l_jⁱ are updated for each pedestrian, namely:

[0238] $\begin{array}{cc}{\stackrel{\_}{\mathrm{\Delta J}}}_j^{T:i}=\frac{\left(N_{\mathrm{mem}}-1\right){\stackrel{\_}{\mathrm{\Delta J}}}_{j-1}^{T:i}+{\stackrel{\_}{\mathrm{\Delta J}}}_j^{T:i}}{N_{\mathrm{mem}}}& \left(41\right)\\ {\stackrel{\_}{l}}_j^i=\frac{\left(N_{\mathrm{mem}}-1\right){\stackrel{\_}{l}}_{j-1}^i+{\stackrel{\_}{l}}_j^i}{N_{\mathrm{mem}}}& \left(42\right)\end{array}$
where

[0239] $\Delta J_j^{T_i}$
is a current level of instantaneous dissatisfaction,

[0240] ${\stackrel{\_}{\mathrm{\Delta J}}}_{j-1}^{T:i}$
is a dissatisfaction norm after completing step j−2, l_jⁱ is a current instantaneous step length,

[0241] ${\stackrel{\_}{l}}_{j-1}^i$
is a feasible step length norm after completing step j−2 and N_mem is the number of memory steps.

[0242] Other updating rules may be used provided the number of memory steps N_mem is obtained a posteriori by fitting empirically to data.

[0243] By comparing the current level of instantaneous dissatisfaction

[0244] $\Delta J_j^{T_i}$
with the norm

[0245] ${\stackrel{\_}{\Delta J}}_{j-1}^{T:i},$
it is established whether the current course appears to be satisfactory, if the instantaneous current level of total dissatisfaction

[0246] $\Delta J_j^{T_i}$
is inferior than or equal to the dissatisfaction norm

[0247] ${\stackrel{\_}{\Delta J}}_j^{T:i},$
or whether dissatisfaction levels are being induced that are higher than what appears to be reasonable to anticipate, if otherwise.

[0248] In the latter case, a perceived habituation-adapted dissatisfaction deficit δJ_j^T:i serves as incentive to deviate, namely:

[0249] $\begin{array}{cc}\delta J_J^{T:i}=\max \left(0,\Delta J_j^{T:i}-{\stackrel{\_}{\Delta J}}_j^{T:i}\right)& \left(43\right)\end{array}$

[0250] The dissatisfaction deficit

[0251] $\delta J_j^{T:i}$
is used to establish first rough estimates of angular bounds to the right (lower angles) and left (higher angles) of the pedestrian's preferred orientation

[0252] ${\theta }_j^{\mathrm{opt}}$
given by equation 14 above.

[0253] The following assumption is made in order to render the habituation deficit of equation 43 into first angular bounds for the search, namely that a reasonable candidate for the next step j should achieve a step length or walking speed not worse than the norm, it should result in a new position of comparable but not worse density (and thus discomfort) and it should induce a comparable level of inconvenience due to friction as defined in equation 5 above.

[0254] Based on these conditions, the dissatisfaction deficit

[0255] $\delta J_j^{T·i}$
can be attributed to the inconvenience due to accelerating/turning defined in equation 16, which yields an angular range:

[0256] $\begin{array}{cc}\cos \varphi =\min \left(1,\max \left(-1,1-\frac{\delta J_j^{T_i}\Delta t^2}{c_i{m\left({\stackrel{\_}{l}}_j^i\right)}^2}\right)\right)& \left(44\right)\\ \Delta {\theta }_j^{i,l,h}=\min \left(\pi ,\max \left(0,\varphi \right)\right)& \left(45\right)\\ \mathrm{where}& \\ \varphi ={\theta }_j^l-{\theta }_{j-1}^l\in \left[0,\pi \right]& \\ {\theta }_j^l\in \left[{\theta }_{j-1}^i-\Delta {\theta }_j^{i·l},{\theta }_{j-1}^i+\Delta {\theta }_j^{i·h}\right]& \end{array}$

[0257] The imposed conditions are conservative and thus inclusive of all possible solutions.

[0258] So far the angular range has been estimated relative to the orientation angle

[0259] ${\theta }_{j-1}^i$
of the just completed step j−1. The estimate is refined by scanning the pedestrian's neighbourhood and determining local conditions, as will now be described in more detail:

[0260] Referring to FIG. 14, a neighbourhood 29, hereinafter referred to as a test area, is defined around the preferred position 30 given by equation 14 and 15 above. Preferably, the test area 29 is in the form of a circle which is large enough to contain a personal space defined by equations 35 and 36 for any feasible pedestrian speed. Thus, the edge of test area 29 is the farthest that the pedestrian need “look” in order to obtain information for making a decision. A typical radius of the test area is between 1.5 and 2.5 meters.

[0261] The test area 29 in divided in four quadrants 29_I, 29_II, 29_III, 2_IV relative to the preferred forward orientation defined in equation 14 above. Each quadrant is scanned independently and so as to extract any relevant information.

[0262] The areas of the test area 29 and four quadrants 29_I, 29_II, 29_III, 29_IV are given by:

[0263] $\begin{array}{cc}\begin{array}{c}{\alpha }_{\mathrm{test}}=\pi R_{\mathrm{test}}^2\\ {\alpha }_0={\alpha }_{\mathrm{test}}/4\end{array}& \left(46,47\right)\end{array}$
where R_test is the radius of the test area 29.

[0264] For each quadrant 29_I, 29_II, 29_III, 29_IV, an estimate is made of the number of neighbours likely to be within it by the time the pedestrian 5 completes step j. This is done by projecting the position of the neighbours at the end of their step on the basis of their velocity and position as prognosticated by the pedestrian 5. It is assumed that a neighbour will continue to move with the same speed and in the same direction when last “observed”, namely that of their last completed step. The number of neighbours so counted is denoted N_x, where the subscript x=I,II,III,IV is the index of the corresponding quadrant 29_I, 29_II, 29_III, 29_IV.

[0265] Referring to FIG. 16, a scan if performed for fixed obstacles 25, 25′. The physical area that is accessible and free of fixed obstacles per quadrant is then calculated. If α_x^o is the area occupied or rendered inaccessible by an obstacle 25, 25′, then an obstacle free area α_x^f within a quadrant may be calculated, namely:
α_x^f=α_q−α_x^o  (48)

[0266] For example, the obstacles 25, 25′ infringe the first, second and third quadrants 29_I, 29_II, 29_III.

[0267] For first and second quadrants 29_I, 29_II, the accessible areas α_I^f,

[0268] ${\alpha }_{\mathrm{II}}^f$
which are free and accessible comprises regions 30_I, 30_II of quadrants 29_I, 29_II to the left of the obstacle 25. For the third quadrant 29_III which entirely contains a smaller obstacle 25′, the accessible area

[0269] ${\alpha }_{\mathrm{III}}^f$
excludes not only a physical area 31 occupied by the obstacle 25′, but also a portion 32 of the quadrant 29_III in the shadow of the obstacle 25′ as viewed from the pedestrian 5. Thus, the accessible area

[0270] ${\alpha }_{\mathrm{III}}^f$
for the third quadrant 29_III comprises the region 30_III excluding the area 31, 32 delimited by a front edge 32 of the obstacle 25 and two lines of sight 33₁, 33₂.

[0271] Having estimated the accessible area per quadrant α_x^f and the number of neighbours contained therein, the personal space per entity α_e is estimated, using:

[0272] $\begin{array}{cc}{\alpha }_e=\max \left({\alpha }_e^{\max },\frac{\sum _{x=I,\mathrm{II},\mathrm{III},\mathrm{IV}}{\alpha }_x^f}{1+\sum _{x=I,\mathrm{II},\mathrm{III},\mathrm{IV}}{N}_x}\right)& \left(49\right)\\ {\alpha }_x^e=\sum _{\begin{array}{c}k=\left\{x,l_{j-1}^k\to 0\right\}\\ x=I,\mathrm{II},\mathrm{III},\mathrm{IV}\end{array}}{\alpha }_e& \left(50\right)\end{array}$
where

[0273] ${\alpha }_e^{\max }$
maximum area allocated per entity, which is an empirically obtained value from fitting data. The personal space per entity α_e is the area which is free of obstacles and which is divided among the neighbouring pedestrians and the pedestrian themselves. However, if the density of pedestrians in the test area 28 is low then the maximum area allocated per entity

[0274] ${\alpha }_l^{\max }$
is used. This is because the pedestrian expands his or her personal space, the fewer neighbors there are in his or her neighbourhood 29. A larger personal space leads to a greater sense of well-being. If, however, there are few or no neighbours infringing the pedestrian's neighbourhood 29, then the pedestrian is content with a maximum area available as personal space. Beyond that, they do not care whether more personal space is available.

[0275] Having determined how much of neighbourhood 29 is free of obstacles 25, how many neighbours are infringing the test neighbourhood 29 and how much personal space per entity can be expected per quadrant, an area of a lane, α_pass, required for passage through the neighbourhood 29 is then estimated using:
α_pass=R_testR₀  (51)

[0276] This area is expected to be available if enough area free of obstacles is available, but not otherwise.

[0277] The net free area α_x of a quadrant 29_I, 29_II, 29_III, 29_IV and forward spatial availability weights w_l,h for the first and fourth quadrants 29_I, 29_Iv are estimated using:
α_x=α_x^f−α_x^e  (52)

[0278] $\begin{array}{cc}\mathrm{if}\left({\alpha }_{I,\mathrm{IV}}^f\ge 4{\alpha }_{\mathrm{size}}\right)\{\begin{array}{c}{\alpha }_{I,\mathrm{IV}}^f-={\alpha }_{\mathrm{pass}}\\ {\alpha }_q-={\alpha }_{\mathrm{pass}}\end{array}& \left(53\right)\\ w_{I,h}=\frac{{\alpha }_{I,\mathrm{IV}}}{{\alpha }_q}& \left(54\right)\end{array}$

[0279] The first and fourth quadrants 29_I, 29_IV are the quadrants where the pedestrian is most likely to look for its next step. The forward spatial availability weights w_l,h, which can take values between zero and unity, express the likelihood that free space is to be found there. Thus, a value of w_l,h=1, where the indices l,h correspond to forward low or high angles respectively, i.e. first and fourth quadrants 29_I, 29_IV, means that the entire quadrant 29_x is fully available and free of obstacles and neighbours. By contrast, a value of w_l,h=0 means that the quadrant 29_x is saturated with obstacles and neighbours and there appears to be no area available to be claimed. Thus, the forward spatial availability weights w_l,h is an important indicator when selecting a quadrant 29_x that is likely to yield a satisfactory solution.

[0280] Having estimated the availability of physical space, the offending neighbours found in the test area 29 are categorized as “friends” or “foes”. Cooperation and competition are extremely important in emergent phenomena induced by the interactions of intelligent agents.

[0281] Referring to FIG. 17, a friend 34 may be classified as a neighbouring pedestrian which appears to be moving in the pedestrian's approximate direction. A foe 35 may be classified on the other hand as a neighbouring pedestrian that is moving in an opposing direction.

[0282] If the density of friends 34 in the neighbourhood 29 is very high, it can enforce synchronization. For a high-density pocket of slow-moving friends 34 lying ahead of the pedestrian 5, if there is insufficient space for overtaking, then the pedestrian 5 is forced to slow down. This synchronization effect is a collaborative phenomenon, which causes a slowing down to speed levels below the preferred speed. Likewise, for a fast-moving, high-density pocket of friends lying behind the pedestrian 5, if there is not enough room to move out of the way, then the pedestrian 5 speeds up.

[0283] Apart from adjustments to the cruising speed, synchronization may also cause re-ordering. In extreme situations at high density, the pedestrian may be forced to take a step only after the person directly ahead has moved and no earlier.

[0284] The density of friends and the apparent synchronization speed are considerations to be taken into account since they enforce deviating from one's preferred speed and therefore act as deterrents. These considerations, however, are only necessary for instantaneous adjustments of the speed and do not need to be “remembered”. This is because cruising speed is resumed when synchronization is no longer necessary.

[0285] For oncoming neighbours, i.e. foes 35, the considerations to be taken into account are somewhat different. The pedestrian is competing rather than collaborating with their foes.

[0286] The higher the density of oncoming foes 35, the higher the probability of collision becomes. Thus, the cost for successfully negotiating and avoiding collision tends to become greater also.

[0287] The density of foes 35 and collision probability are important factors for consideration. Unlike synchronization, which can be taken into account instantaneously, collision probability is remembered to facilitate future intelligent decisions. Thus, in high-volume multi-directional traffic one should not only take into account the instantaneous physical presence of oncoming foes, but also any history of foes. The history or memory of past collision probabilities serves to project the likelihood that one might encounter yet-invisible foe downstream, even if not quite yet in sight, by which time it may be too late for corrective manoeuvring.

[0288] For friends and foes, a cooperation weight

[0289] $w_{k;j}^{\square }$
and competition weight

[0290] $w_{k;j}^{\perp }$
assigned by the pedestrian 5 to each friend 34 and foe 35 respectively who are projected be in the test area 29 by the end of step j are:

[0291] $\begin{array}{cc}{w}_{k;j}^{\square }=\frac{1}{2}\left[1+\cos \left({\theta }_j^{i;\mathrm{opt}}-{\theta }_{j-1}^k\right)\right]& \left(55\right)\\ w_{k;j}^{\perp }=\frac{1}{2}\left[1-\cos \left({\theta }_j^{i;\mathrm{opt}}-{\theta }_{j-1}^k\right)\right]& \left(56\right)\end{array}$

[0292] The assignment is on the basis of the extent to which the projected direction of motion of a neighbour appears to be parallel or anti-parallel to that of the pedestrian using equations 19 to 24 above.

[0293] For friends, the position

[0294] ${\stackrel{\rightharpoonup }{r}}_j^{ik}$
and angle

[0295] ${\theta }_j^{ik}$
relative to the position and direction of pedestrian 5 are calculated using:

[0296] $\begin{array}{cc}{\stackrel{\rightharpoonup }{r}}_j^{ik}=\left(x_{j+1}^k-x_{j+1}^i\right)\hat{x}+\left(y_{j+1}^k-y_{j+1}^i\right)\hat{y}& \left(57\right)\\ {\theta }_j^{ik}={\cos }^{-1}\left(\frac{\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^i·{\stackrel{\rightharpoonup }{r}}_j^{ik}}{\delta {\stackrel{\rightharpoonup }{r}}_{j,j+1}^i{\stackrel{\rightharpoonup }{r}}_j^{ik}}\right)& \left(58\right)\end{array}$

[0297] These parameters lead to estimates of forward, lateral, and combined proximity weights

[0298] $w_{k,j}^{f,l,\mathrm{prox}},$
namely:

[0299] $\begin{array}{cc}{w}_{k;j}^f=\min \left(0,1-\frac{{\stackrel{\rightharpoonup }{r}}_{j+1}^i-{\stackrel{\rightharpoonup }{r}}_{j+1}^k\cos {\theta }_j^{ik}-R_0^i-R_0^k}{R_{\mathrm{test}}-R_0^i-R_0^k}\right)& \left(59\right)\\ w_{k;j}^l=\min \left(0,1-\frac{{\stackrel{\rightharpoonup }{r}}_{j+1}^i-{\stackrel{\rightharpoonup }{r}}_{j+1}^k\sin {\theta }_j^{ik}-R_0^i-R_0^k}{R_{\mathrm{test}}-R_0^i-R_0^k}\right)& \left(60\right)\\ w_{k;j}^{\mathrm{prox}}=w_{k;j}^f{w}_{k;j}^l& \left(61\right)\end{array}$

[0300] Thus, the nearer a friend 34 is to the pedestrian 5 in both forward and lateral sense, then the more it enforces speed synchronization.

[0301] Lastly, weighted counts of friends 34 and foes 35 per quadrant and corresponding densities ρ_x^□, ρ_l^⊥, ρ_h^⊥ are determined:

[0302] $\begin{array}{cc}{n}_x^{\parallel }=\sum _{\underset{x-I,\mathrm{II},\mathrm{III},\mathrm{IV}}{k\in x}}{w}_{k,j}^{\parallel }{w}_{k,j}^{\mathrm{prox}}\Theta \left(\cos \left({\theta }_j^{l\mathrm{opt}}-{\theta }_{j-1}^k\right)\ge \cos {\theta }_{\parallel }\right)& \left(62\right)\\ n_x^{\perp }=\sum _{\underset{x-I,\mathrm{II},\mathrm{III},\mathrm{IV}}{k\in x}}{w}_{k,j}^{\perp }\Theta \left(\cos \left({\theta }_j^{l·\mathrm{opt}}-{\theta }_{j-1}^k\right)<\cos {\theta }_{\parallel }\right)& \left(63\right)\\ {\rho }_x^{\parallel }=\frac{n_x^{\parallel }}{{\alpha }_x}& \left(64\right)\\ {\rho }_l^{\perp }=\frac{n_I^{\perp }+n_{\mathrm{II}}^{\perp }}{{\alpha }_I+{\alpha }_{\mathrm{II}}}& \left(65\right)\\ {\rho }_h^{\perp }=\frac{n_{\mathrm{III}}^{\perp }+n_{\mathrm{IV}}^{\perp }}{{\alpha }_{\mathrm{III}}+{\alpha }_{\mathrm{IV}}}& \left(66\right)\end{array}$

[0303] The step Θ function enforces the condition in parenthesis. Thus, if the condition is true, then the Θ function is equivalent to unity, otherwise zero. The parameter θ_// is set empirically to π/3. Thus, neighbours whose direction of motion is to within θ_// on either direction (i.e. higher or lower) from that of pedestrian 5 are considered as moving in a similar direction and are counted as friends 34, thus resulting in collaboration and synchronization. Those neighbours, however, whose direction of motion falls outside this range are counted as foes 35 and contribute to competition in the form of higher probability for collisions.

[0304] The process described in relation to equations 59 to 66 and extracting information relating to neighbouring pedestrians is referred to as scanning the neighbourhood 29 in the vicinity of the pedestrian 5 and assessing local conditions. The information derived from computation of equations 59 to 66 is subsequently used to establish criteria applied in restricting the search space.

[0305] Starting with the density of foes 35, a probability of collision towards lower or higher angles translates into a probability that the pedestrian 5 will be on a collision course with an offending neighbour should it decide to deviate to the right (i.e. lower angles) or left (higher angles) of its optimal orientation as defined in equation 14. This probability requires further refinements of the angular acceptance range derived earlier in equation 53.

[0306] In summary, the information relating to the density of foes 34 in the test area 39 is used to impose angular restrictions in the search space of acceptable feasible candidate next steps and to decide whether seeking a solution toward the left or right of the optimal orientation is more profitable.

[0307] An instantaneous competition strength

[0308] $p_{l;h}^{\perp }$
is derived from the instantaneous information foe density

[0309] ${\rho }_{l;h}^{\perp }$
and the estimated personal space per entity α_e, namely:

[0310] $\begin{array}{cc}{p}_{l,h}^{\perp }=\min \left(l,{\rho }_{lh}^{\perp }{\alpha }_c\right)& \left(67\right)\end{array}$

[0311] This admits values between zero (collision impossible) and unity (collision certain) for either side (index l for lower angles, or to the right of the optimal orientation, and h for higher angles or to the left).

[0312] A collision probability memory

[0313] ${\stackrel{\_}{p}}_{l;h}^{\perp }$
maintained by the pedestrian 5 and updated according to the rules described earlier is defined using a dynamic memory length N_m^⊥ (expressed using C++ programming convention), i.e.:

[0314] $\begin{array}{cc}{\stackrel{\_}{p}}_{l,h}^{\perp }=\frac{\left(N_m-1\right){\stackrel{\_}{p}}_{l,h}^{\perp }+p_{l,h}^{\perp }}{N_m^{\perp }}& \left(68\right)\\ N_m^{\perp }=\left(p_l^{\perp }\ge \epsilon ||p_h^{\perp }\ge \epsilon \right)?\min \left(++N_m^{\perp },N_{\max }\right):\max \left(--N_m^{\perp },1\right);& \left(69\right)\end{array}$

[0315] The memory length N_m^⊥ corresponds to the number of steps over which memory is maintained and N_max is set to 10. Thus, from the moment a foe 35 is detected, a collision probability memory starts to be built for the pedestrian 5 for up to ten steps. Similarly, when foes 35 are no longer detected, the pedestrian begins to “forget”. If no foes are detected over the course of ten consecutive steps, then there is no memory of earlier collision information. Foe collision information begins to accumulate it anew when the next foe is detected. The cap of ten steps amounts to a medium-term memory and has been determined empirically from fitting to data.

[0316] There may also be empirical rules for resetting memory. For example, if the environment changes dramatically in such a way that the new conditions no longer correspond to earlier experience, a mechanism may be used to erase memory, reset the memory length and begin rebuilding memory afresh. An example of when this may happen is if the pedestrian steps out of a concourse, characterised by busy multi-directional motion, and into a corridor, characterised by unidirectional low-volume traffic.

[0317] Thus, the updated collision probability memory becomes the perceived collision probability of the pedestrian 5 at time step j. This is used to derive the left-right asymmetry P^⊥ (expressed using C++ programming convention), namely:

[0318] $\begin{array}{cc}{P}^{\perp }=\left({\stackrel{\_}{p}}_l^{\perp }\ge \varepsilon \parallel {\stackrel{\_}{p}}_h^{\perp }\ge \varepsilon \right)?\frac{{\stackrel{\_}{p}}_l^{\perp }-{\stackrel{\_}{p}}_h^{\perp }}{{\stackrel{\_}{p}}_l^{\perp }+{\stackrel{\_}{p}}_h^{\perp }}:0;& \left(70\right)\end{array}$
which amounts to a measure of how much more likely it is to encounter a collision in deviating on one side of the optimal orientation as opposed to the other.

[0319] So far, the asymmetry construed by pedestrian 5 is entirely dynamic, depending exclusively on its own reading of signals from its surroundings. Hence, it is fully emergent. This asymmetry is the main reason for complex emergent patterns such as the spontaneous formation of lanes above a critical density in multi-directional environments.

[0320] Spatial or cultural bias may be introduced, should there be need for one, using:

[0321] $\begin{array}{cc}{P}^{\perp }=\min \left(1,\max \left(-1,P^{\perp }+P_{\mathrm{bias}}^{\perp }\right)\right)& \left(71\right)\end{array}$

[0322] The term ΔP_bias^⊥ allows introduction of a forced, rather than emergent, bias or preference to the left or right. Such as bias may be induced, for example using a sign “keep to the right”, or a cultural habit, such as keeping to the right in continental Europe or keeping to the left in the UK.

[0323] A preliminary range δθ_l,h, relative to the preferred orientation

[0324] ${\theta }_j^{i:\mathrm{opt}}$
of equation 14, may be derived using equation 45, namely:

[0325] $\begin{array}{cc}\delta {\theta }_{lh}=\min \left(\pi ,\max \left(0,\Delta {\theta }_j^{i,l,h}\pm {\theta }_j^{i,\mathrm{opt}}\mp {\theta }_{j-1}^i\right)\right)& \left(72\right)\end{array}$

[0326] The left-right asymmetry is used to redistribute the angular range from the least to the more favourable side, which leads to (expressed using C++ programming convention):
δθ_asym=(P^⊥≧0)?P^⊥w_lδθ_l:−P^⊥w_hδθ_h;  (73)
which is the range of angles to be removed from an unfavourable side and added to a favourable one. For example, an angular range is derived using equation 54. A first range of angles to be scanned for candidate solutions is to the right of the preferred orientation and a second range of angles is to the left. If the left-right asymmetry relation turns out to favour the left in preference to the right, a slice of angles δθ_asym is removed from the right side and added to the left side. To the extent that the pedestrian 5 deems it more likely to collide with a foe on the right than on the left, means that the pedestrian 5 does not look as far to the right for its next step as it would have done if there had been no foes. Instead it looks farther to the left since collisions are less likely.

[0327] Making use if this information, the angular range is finally corrected yielding a final range Δθ_j^i;l,h of least competition, namely:

[0328] $\begin{array}{cc}\Delta {\theta }_j^{i;l,h}=\min \left({\mathrm{\delta \theta }}_{l,h},\max \left(0,w_{l,h}\left(1-p_{l,h}^{\perp }\right){\mathrm{\delta \theta }}_{l,h}\mp {\mathrm{\delta \theta }}_{\mathrm{asym}}\right)\right)& \left(74\right)\end{array}$

[0329] This is the range of angles to the right

[0330] $\left(\Delta {\theta }_j^{i:h}\right)$
and left

[0331] $\left(\Delta {\theta }_j^{i:l}\right)$
relative to the preferred angle

[0332] ${\theta }_j^{i;\mathrm{opt}}$
given in equation 23 where the pedestrian 5 seeks an acceptable candidate for the j^th step.

[0333] Finally, a preferentiality p_l,h to either side is determined, where p_l,h take on values between zero and unity (expressed using C++ programming convention):

[0334] $\begin{array}{cc}{p}_{l,h}=\left(\Delta {\theta }_l=\Delta {\theta }_h=0\right)?\frac{1}{2}:\frac{1}{2}\left[1\pm \frac{\Delta {\theta }_l-\Delta {\theta }_h}{\Delta {\theta }_l+\Delta {\theta }_h}\right];& \left(75\right)\end{array}$

[0335] The higher the value of p_l,h, the higher the preferentiality.

[0336] The density of friends and the effect of synchronization will now be described in more detail:

[0337] First, an instantaneous density u_x of friends per quadrant of the test area 29 is translated into a strength of cooperation, admitting values between zero and unity:
u_x=min(1, ρ_xα_e)  (76)

[0338] The larger the more likely to be forced to synchronize). As explained earlier, cooperation arises as and when needed, i.e. instantaneously. It does not help to prevent errors in the future the way the collision probability does. Thus, no memory of it is kept.

[0339] A weighted average of step length l_x, or equivalently speed, of all the friends in the neighbourhood (per quadrant) is estimated:

[0340] $\begin{array}{cc}{\stackrel{\_}{l}}_x=\frac{\sum _{\underset{x=I,\mathrm{II},\mathrm{III},\mathrm{IV}}{k\in \left(\text{friend in qudrant}x\right)}}{l}_{j-1}^i{w}_{k,j}^{\parallel }{w}_{k,j}^{\mathrm{prox}}}{\sum _{\underset{x=I,\mathrm{II},\mathrm{III},\mathrm{IV}}{i\in \left(\text{friend in qudrant}x\right)}}{w}_{k,j}^{\parallel }{w}_{k,j}^{\mathrm{prox}}}& \left(77\right)\end{array}$

[0341] Slower neighbours behind the pedestrian do not matter because they do not catch up. Likewise, faster neighbours ahead do not matter since the pedestrian does not catch up. In either case, the pedestrian may continue walking at their preferred speed.

[0342] Faster neighbours behind, on the other hand, can have a chasing effect. They may exert pressure on a pedestrian ahead of them to either move faster or get out of the way. Likewise, slower neighbours in front may force an undesirable slowing down. Hence, synchronization is relevant when there are slower neighbours in front or faster neighbours behind.

[0343] This bias is reflected in forward and backward synchronisation weights,

[0344] $u_{I,\mathrm{IV}}^{\prime },$

[0345] $u_{\mathrm{II},\mathrm{III}}^{\prime }$
(expressed using C++ programming convention), namely:

[0346] $\begin{array}{cc}{u}_{I,\mathrm{IV}}^{\prime }=\left({\stackrel{\_}{l}}_{I,\mathrm{IV}}>l_j^{i;\mathrm{opt}}\left(\theta \right)\right)?0:u_{I,\mathrm{IV}};& \left(78\right)\\ u_{\mathrm{II},\mathrm{III}}^{\prime }=\left({\stackrel{\_}{l}}_{\mathrm{II},\mathrm{III}}>l_j^{i;\mathrm{opt}}\left(\theta \right)\right)?0:u_{\mathrm{II},\mathrm{III}};& \left(79\right)\end{array}$

[0347] The forward and backward synchronization strength

[0348] $u_{I,\mathrm{IV}}^{\prime }{u}_{\mathrm{II},\mathrm{III}}^{\prime }$
depend on the density of friends and the degree of alignment of their orientation with the desired orientation of entity i.

[0349] To the extent that

[0350] $u_{I,\mathrm{IV}}^{\prime }$
and

[0351] $u_{\mathrm{II},\mathrm{III}}^{\prime }$
impose external synchronization due to dynamical external conditions in the neighbourhood outside the pedestrian's control, the pedestrian is forced to degrade the weight of its own free will, i.e. to maintain the preferred step length or preferred speed. This leads to a weight of the pedestrian's own free u_opt which is updated after taking into account external constraints, namely:

[0352] $\begin{array}{cc}{u}_{\mathrm{opt}}=1-u_{I,\mathrm{IV}}^{\prime }-u_{\mathrm{II},\mathrm{III}}^{\prime }& \left(80\right)\end{array}$

[0353] Combining the weights of the various components, another estimate may be made of the feasible step length

[0354] $l_{l,h}^{i,j}$
on the basis of its own desires adjusted to external constraints (expressed using C++ programming convention), namely:

[0355] $\begin{array}{cc}{l}_{l,h}^{i;j}=\left(u_{\mathrm{opt}}>0\right)?u_{\mathrm{opt}}{l}_j^{i;\mathrm{opt}}\left(\theta \right)+u_{I,\mathrm{IV}}^{\prime }{\stackrel{\_}{l}}_{I,\mathrm{IV}}+u_{\mathrm{II},\mathrm{III}}^{\prime }{\stackrel{\_}{l}}_{\mathrm{II},\mathrm{III}}:\frac{u_{I,\mathrm{IV}}^{\prime }{\stackrel{\_}{l}}_{I,\mathrm{IV}}+u_{\mathrm{II},\mathrm{III}}^{\prime }{\stackrel{\_}{l}}_{\mathrm{II},\mathrm{III}}}{{\stackrel{\_}{l}}_{I,\mathrm{IV}}+u_{\mathrm{II},\mathrm{III}}^{\prime }}& \left(81\right)\end{array}$

[0356] Thus, the pedestrian will no longer strive to achieve the unrealistic step length

[0357] $l_j^{i:\mathrm{opt}}$
which it would have preferred based on equation 21. While searching for a compromise solution,

[0358] $l_j^{i;\mathrm{opt}}$
becomes the “adjusted” preferred step length which is inserted in place of the preferred step length when minimizing the full dissatisfaction function. By contrast, the instantaneous preferred speed and resultant instantaneous preferred step length were used when minimizing self-dissatisfaction during the first stage. By now, the pedestrian has deemed this preference unrealistic and, after taking into account local information, has learned what is realistic and adjusted their speed preference accordingly. Thus, it considers a more realistic step length

[0359] $l_{l,h}^{i,j}$
which is the best it can do given the synchronization constraints imposed upon it by the environment.

[0360] A threshold l_thr, empirically set to 5 cm, is introduced to prevent agitation for the conditions:

[0361] $\begin{array}{cc}\mathrm{if}\left(l_{l,h}^{i;j}<l_{\mathrm{thr}}\right)l_{l,h}^{i;j}=0;& \left(82\right)\end{array}$

[0362] This may be used, for example, in situations where pedestrians file into a bottleneck and the adjusted step length turns out to be extremely small. According to equation 82, if the feasible step length turns out to be less that the threshold, pedestrians consider themselves blocked and maintain their previous position until their neighbourhood clears. When the neighbourhood clears a longer step length is allowed.

[0363] A step length deficit

[0364] $\delta l_{l,h}^{i;j}$
is defined as:

[0365] $\begin{array}{cc}\delta l_{lh}^{i,j}=\frac{l_{l,h}^{i,j}-l_j^{i,\mathrm{opt}}}{l_{l,h}^{i,j}+l_j^{i,\mathrm{opt}}}& \left(83\right)\end{array}$
and is a normalised measure of the difference between the adjusted step length and the preferred step length, taking values between 0 (when the preferred and feasible lengths identical) and 1 (when the difference between preferred and feasible step lengths is greatest. It is a measure of preferentiality of the adjusted step length.

[0366] A preferentiality of one side over the other may be defined (expressed using C++ programming convention) using:

[0367] $\begin{array}{cc}{q}_{l,h}=\left(\delta l_l=\delta l_h=0\right)?\frac{1}{2}:\frac{1}{2}\left[1\mp \frac{\delta l_l-\delta l_h}{\delta l_l+\delta l_h}\right];& \left(84\right)\end{array}$

[0368] Preferentiality uses the proximity of an apparent feasible step length on either side to one's own preference as a criterion. If the preferentiality for both left and right is the same, then q₁=q_r=½.

[0369] The second stage of micro-navigation ends with the determination of a favourite side, right (l) or left (h), namely:

[0370] $\begin{array}{cc}\begin{array}{c}{Q}_{l,h}=q_{l,h}{p}_{l,h}{\alpha }_{I,\mathrm{IV}}^f\\ \mathrm{if}\left(Q_l>Q_h\right)j=l,\\ \mathrm{else}\mathrm{if}\left(Q_l<Q_h\right)j=h;\\ \mathrm{else}j=\left(\mathrm{mdm}\left(\right)>0.5\right)?l:h;\end{array}& \left(85\right)\end{array}$

[0371] In the case of a draw, a dice is thrown.

[0372] In summary, the second stage of micro-navigation establishes an angular range for a search, for deviations on either side of the ideal orientation while looking for an acceptable candidate, adjusts the preferred speed (or step length) to a feasible speed as close as possible to the pedestrian's preferred speed and determines the favourite side from which to launch the search.

Micro-Navigation: Stage III

[0373] During the first stage of micro-navigation, self-dissatisfaction is minimised so as to identify a preferred step to a preferred position. If the preferred position is available and no discomfort is associated with it, the pedestrian can proceed to take this step. However, if either the preferred position is unavailable or there is some discomfort associated with it due the presence of either offending neighbours or fixed obstacles then the second and third stages are brought into play.

[0374] During the second stage of micro-navigation, upper and lower angular bounds are found relative to a preferred orientation. Between these angular bounds candidate solutions may be sought. Finally, it is determined which side (left or right) of the preferred orientation appears preferable when looking for a candidate solution first. Thus a subspace is defined. Moreover, the preferred speed requirement is adjusted for each side to reflect dynamical conditions imposed upon the pedestrian by its surroundings, to a value that appears more reasonable to attempt to achieve on the basis of local conditions.

[0375] During the third stage, a detailed search is performed to determine and execute the pedestrian's next step. This will now be described in more detail:

[0376] Referring to FIG. 17, the pedestrian 5 has a preferred orientation

[0377] ${\theta }_j^{\mathrm{opt}}$
indicated by reference numeral 36.

[0378] A final search is begun. Starting from the preferred orientation θ_j^opt and turning towards a preferred side 37, for example to the right, a solution is sought which minimizes the total dissatisfaction of equation 40. This comprises solving equations of motion, namely:

[0379] $\begin{array}{cc}\frac{d}{dl}\Delta J_T{|}_{l_j,{\theta }_j}=0& \left(86\right)\\ \frac{d}{d\theta }\Delta J_T{|}_{l_j,{\theta }_j}=0& \left(87\right)\end{array}$

[0380] A heuristic algorithm is used to solve the equations of motion.

[0381] This is contrasted with minimization of self-dissatisfaction during the first stage of micro-navigation, which results in a preferred orientation angle and step length.

[0382] The main difference is in that whereas the preferred solution is obtained in a self-referential manner without regard to the possible presence of neighbours and obstacles, the final solution takes these into account. In particular, the presence of offending neighbours and obstacles now induces discomfort.

[0383] A search for a compromise step is conducted varying orientation angle θ_jⁱ and step length l_jⁱ.

[0384] Starting from the preferred angle

[0385] ${\theta }_j^{i;\mathrm{opt}}$
and turning first towards the preferred side determined using equation 85, step length l is varied starting from l=0, i.e. the current location. At each orientation angle θ_jⁱ, a check is made is whether there are any entities or obstacles impeding passage. If there is, then the step length l_jⁱ is varied only as far as the entity or obstacle. Otherwise, the limit is the adjusted step length

[0386] $l=l_{l,h}^{i;j}.$
The search continues on the preferred side as up to the limit