An early-stage design model for estimating ship evacuation patterns using the ship-centric Markov decision process

Abstract

An early-stage design model is presented that estimates personnel locations on board a vessel during times of evacuation. This model takes into account various levels of uncertainty and pain that individuals may feel while heading toward safety, while simultaneously not requiring highly detailed information regarding the vessel layout. This makes this model suitable for analysis during early stages of design. To do this, principal eigenvector analysis is applied to the ship-centric Markov decision process model. Principal eigenvector analysis provides a leading indicator metric for forecasting and quantifying locations of individuals when coupled with the ship-centric Markov decision process model. For evacuation models suited for later stages of design, full temporal simulations may be required to understand long-term implications of personnel movement. This article proposes an alternative method that is able to identify some of these implications while not requiring full details of the vessel layout nor temporal simulations. To do this, a common theorem in Markov theory is applied that defines how the principal eigenvector represents the long-term steady-state behavior of the system. Metrics are defined that quantify the probability that an individual will congregate at specific locations on the vessels and highlight sensitivities to long-term behavior. A case study of a simplified vessel layout is presented that examines decision-making regarding ship egress analysis and general arrangements design. The results highlight specific areas of interest that cause significant changes to where individuals congregate and the probability they arrive safely at the exit. Sensitivity studies are performed varying the uncertainty in the movement of the individuals, how much pain they are experiencing, and one example where a passageway is blocked.

Keywords

Evacuation analysis early-stage ship design Markov decision process eigenvector analysis uncertainty analysis

Introduction

During early stages of ship design, it is difficult to study personnel movement patterns given the inherent uncertainty of the ship layout during that stage of design and the vast number of combinations of personnel distributions that may exist in the vessel at any given time during its lifecycle. This desire to study personnel movements may come from safety, regulatory, or financial reasons. Understanding how individuals move about the vessel during an emergency is not only necessary for increasing the safety of the vessel but also mandated by some regulatory bodies. The International Maritime Organization (IMO)¹ has published guidelines specifically for analyzing evacuation patterns for passenger ships, while the Safe Return to Port regulations² may necessitate studying personnel movement because of the desire to learn how to move individuals from one compartment to another if one area becomes flooded. There are also financial reasons to study personnel movement. For instance, a cruise ship may want to understand how passengers move around so they can strategically place shops and restaurants near high-traffic areas to maximize their profit potential.

However, as the size and complexity of vessels increase, the problem of understanding personnel movement patterns during early-stage design becomes harder. There may be uncertainty over the details regarding layout of the vessel^3,4 or even the movement of individuals. For instance, a paid crew who knows the ship well will behave different in an emergency than a paying customer on a cruise ship who may have just boarded the vessel or who may have limited mobility.⁵ Properly accounting for this uncertainty is both difficult and important. Uncertain movements will affect where individuals congregate during times of emergency. Ahola et al.⁶ discuss how passengers’ perception of safety on cruise ships may also affect their behavior and should thus be taken into account when evaluating technical portions of the design. For instance, some passengers in a cruise ship may get disoriented during power outages, or smoke from a fire may impair visibility and judgment. During these situations, some on board may not make it to the safety point, such as a lifeboat. During the Costa Concordia disaster, 32 passengers died, in part, because they were unable to make off of the ship despite the fact the ship was immediately close to shore and the emergency took some time to develop. It took salvage efforts years before they could find all deceased passengers.⁷ It is situations like these that make studying personnel movement to understand where people may congregate so important.

Studying personnel movement effectively and accurately has traditionally required detailed general arrangements and the physical distribution of the individuals on board. Methods such as multi-agent simulations^8,9 or velocity-based personnel movement models¹⁰ have been developed that provide a good estimation of this behavior onboard ships. However, these methods require significant details and may be computationally expensive and are likely better suited for later stages of design when the design has become more mature. Rigterink et al.¹¹ developed a method to study the ship layout from a personnel perspective without the need for detailed information. They applied network science metrics to identify potential choke points in the layout that may cause congestion. Their attempt was to study the impact of a vessel layout given limited information. To accomplish this, they omitted modeling the movement of individuals and instead focused solely on the layout.

This article presents a method for estimating where individuals may congregate without the need for detailed information, while also incorporating uncertain personnel movements. This method accounts for uncertainty in movements and the pain individuals may feel, while at the same time not requiring knowledge of where individuals are at the start of the emergency, nor full temporal simulations. The final location of the individuals is estimated probabilistically. In this sense, this method provides information that may be beneficial during early-stage design when the layout of the vessel is still being designed and prior to more detailed personnel movement analyses that may be required later in the design process.

To do this, principal eigenvector analysis is applied to the ship-centric Markov decision process (SC-MDP) model. MDPs were first applied to ship design and decision-making by Niese and Singer¹² as a way to analyze predictive time domain decisions related to ship design and operation. The SC-MDP model involves applying MDPs to ship design and decision-making. The SC-MDP model has been chosen for this problem because it is capable of incorporating stochastics and temporal implications in analyzing maritime decision-making problems. The benefits of the model include a state-based representation of the system attributes and uncertain external environment, the capability to model various decision scenarios, and the ability to model uncertain temporal changes.¹³ Kana and Singer⁵ introduced how to use this model to simulate the uncertain decisions individuals may make while searching for an exit during times of emergency.

The work presented in this article differentiates itself from the previous SC-MDP work both in the applications and derived metrics. Kana and Singer⁵ tried to quantify changes in decision-making of how individuals move about using the eigenvalues of the system. This article, on the other hand, aims to understand probabilistically where individuals may eventually congregate during emergency situations. This is done by examining the principal eigenvectors.

Previous work on the SC-MDP model is extended by examining the utility of the principal eigenvectors in predicting probabilistically where individuals may congregate without the need for temporal simulations. While no single model can capture all aspects of personnel movement during the uncertain early-stage design, the objective of this research is to provide a unique perspective on the problem to help elicit new insight that may improve understanding and design. A case study is presented that explores this method on a problem involving ship egress analysis and general arrangements design. This case study is an extension of the one presented by Kana and Singer.⁵

There are two primary objectives:

To demonstrate how to probabilistically estimate where individuals may congregate during ship emergency situations using principal eigenvector analysis applied to the SC-MDP model.

To show the relationship between the principal eigenvectors of the SC-MDP model discussed in this article and the eigenvalues presented in Kana and Singer.⁵ To accomplish this second objective, the same case study setup as presented by Kana and Singer⁵ has been used; however, new methods, metrics, and analyses have been added which are unique to this article.

Methods

This article uses the SC-MDP model to simulate probabilistically where individuals may congregate throughout the vessel during an emergency situation. An overview of the methods is presented first, followed by its specific application to the ship evacuation problem. The SC-MDP model is based on the MDP. MDPs are an extension of Markov chains, which model probabilistically how a process evolves through time, given the assumption that future dynamics are independent of past events. Modeling the probability that a system will change from one state to another is given by transition matrix, M , shown in equation (1), where $m_{i, j}$ denotes a specific probability. For Markov processes $\sum_{j} m_{i, j} = 1$

M = [\begin{matrix} m_{1, 2} & m_{1, 2} & \dots \\ m_{2, 1} & m_{2, 2} & \dots \\ ⋮ & ⋮ & ⋱ \end{matrix}]

(1)

The probability of being located in a specific state is given by the state vector, s , as defined in equation (2)

s = (s_{1}, s_{2}, \dots, s_{n})

(2)

The state vector may vary over time, and this evolution is calculated by multiplying s with M ; see equation (3).¹⁴ For this article, the individual states will represent specific rooms in the ship, and $s_{i} \in s$ gives the probability a person is located in a specific room. In this way, $s^{t}$ models probabilistically where individuals are located through time

s^{t + 1} = s^{t} M

(3)

However, Markov chains alone are not able to simulate the pain individuals may experience during evacuation nor the various decisions that individuals may make. Extending the Markov chain model to include various decisions and expected utilities defines an MDP. MDPs are designed to handle uncertain sequential decision-making problems. Four parts make up the standard MDP: a set of states, S, of the system; a set of actions, A, that can be taken; a set of transitions, T, that map the probability of moving from one state, s, to a new state, s′, after following a specific action, a; and a set of rewards, R, received for landing in a state after taking an action. Essentially, MDPs can be thought of as a series of action-dependent Markov chains with rewards,¹⁵ where each action can be represented by its own transition matrix.

MDPs are designed to calculate the optimal set of decisions that maximize the expected utility of the system. These decisions are found by calculating the policy, $π$ , of the system, defined in equation (4). The expected utility is calculated using the Bellman equation (equation (5)). Here, U is the expected utility, and $γ$ is the discount factor. Equations (4) and (5) are presented as they are in Russell and Norvig¹⁶

π (s) = \arg max_{a} \sum_{s'} T (s, a, s') U (s')

(4)

U (s) = R (s) + γ max_{a} \sum_{s'} T (s, a, s') U (s')

(5)

Principal eigenvector analysis

This sequence of steps to obtain the principal eigenvectors follows the standard process used to generate the eigenvalues and eigenvectors of the MDP, as also applied in Kana and Singer.⁵ To obtain the eigenvectors of the Markov process, the following steps are performed:

Solve the Bellman equation to obtain the set of decisions and expected utility of the system (equations (4) and (5)). This research used the value iteration algorithm to solve the Bellman equation, defined in Russell and Norvig.¹⁶

From the decision policy, $π$ , generate a series of representative transition matrices, M , that represent the behavior of the system. To generate these transition matrices, select the transition probabilities from each state for each optimal action matrix and place it in the respective row in the resultant transition matrix. For instance, if Action i is optimal for State j, then the jth row of the resultant transition matrix is identical to the jth row of the ith Action transition matrix. A detailed description of this step in the process, including examples, can be found in Sheskin¹⁵ and Kana and Singer.⁵ This step is shown graphically in Figure 1. Here, individual rows from the respective action transition matrices are transferred to the representative transition matrix, M .

Perform eigenvector analysis on the representative transition matrices, M , to generate the eigenvalues and eigenvectors of the MDP. The eigenvalues, $λ_{i}$ , and eigenvectors, $w_{i}$ , are defined in the traditional sense (equation (6)). This research used a built-in MATLAB function to solve this equation

w_{i} M = λ_{i} w_{i}

(6)

Figure 1.

Visual representation of how to convert a series of action-dependent transition matrices to a representative transition matrix, M . Selecting which action transition matrix to select for each state is defined according to the decision policy, $π$ .

The principal eigenvector as a metric for steady-state behavior

A brief derivation of how the principal eigenvector of a regular Markov process can be used as a metric for steady-state behavior is presented, and a more detailed explanation can be found in Anton and Rorres.¹⁴ First, assume a stationary regular Markov process where M does not vary with time and assume some initial state vector, $s^{0}$ . As the system evolves through time, the state vector will eventually converge to a steady-state vector, that is $s^{t} \to s^{\infty} = s$ . This process is shown in equation (7)

\begin{matrix} s^{0} M = s^{1} \\ s^{1} M = s^{2} \\ \dots \\ sM = s \end{matrix}

(7)

The final step in equation (7) can be defined as a eigenvalue equation with s representing the eigenvectors and with the assumption that $λ = 1$ . In this sense, the final line in equation (7) is identical to equation (6). For Markov matrices, not only does $λ = 1$ exist but it is also the largest eigenvalue in magnitude.¹⁷ Thus, the principal eigenvector of M can be used to give the steady-state behavior of the system. This derivation is applicable to this model because the representative transition matrices developed by the MDP (Step 2 above) are Markov chain transition matrices.¹⁵ These representative transition matrices are by definition square stochastic.¹⁴

However, this method is not applicable in all situations. It can only be applied as described when the dominant eigenvalue is unique. In situations where the dominant eigenvalue is repeated, the principal eigenvector itself may also not be unique. Kana¹⁸ presents a modified method for applying eigenvalue analysis to the SC-MDP model when the dominant eigenvalue is repeated. Also, much of the research into the eigenvector properties of Markov processes involves stationary transition probabilities. That is, they do not change with time. This article explores the applicability of these methods for maritime systems that may be non-stationary.

These methods are still applicable to non-stationary processes because for every instant that is defined by M , the steady-state distribution can be calculated without having to run the simulation through time. Thus, the system converges based solely on the set of decisions, defined by M , and not on the initial conditions of the system. In these situations, the projected outcome is entirely independent from where the system starts. This means that the principal eigenvector can be used as a leading indicator metric for projecting where individuals congregate without the need for full temporal simulations. In the case presented, this means that this model can predict where individuals may eventually congregate without the need to run the entire simulation through time.

As decisions change through time, and thus as M changes, the steady-state distribution may change as well. Calculating the magnitude of this change will be used as a means to quantify the effect of a given decision change on the future effect of the system. This article proposes using the magnitude of the angle between the vectors as a way of calculating this change. This angle is calculated using the identity presented in equation (8),¹⁴ where $w_{0}$ is the principal eigenvector associated with the original set of decisions and $w_{1}$ is the principal eigenvector for the system with the updated set of decisions

θ = \cos^{- 1} (\frac{w_{0} \cdot w_{1}}{| | w_{0} | | | | w_{1} | |})

(8)

Thinking of the eigenvector as a vector pointing in the direction of how the instantaneous system will evolve given a set of decisions, it becomes clear that this metric is a leading indicator for analyzing the impact of decisions on a system. For instance, given the current set of behavioral decisions, the location of people on board a vessel, as characterized by a state vector, will eventually congregate to the locations characterized by the eigenvector. This is represented graphically in Figure 2. Here, $w_{i}$ are independent eigenvectors associated with a given set of decisions. As stated, these eigenvectors are identical to the future steady state of the system. Visualization techniques are especially helpful for when the state-space is large.

Figure 2.

Visual representation of the principal eigenvectors as a leading indicator for the impact of decisions. $w_{i}$ are independent eigenvectors associated with a given set of decisions which are identical to the future steady state of the system.

Case study: personnel movement and ship egress analysis

The following case study is designed to show the utility of the proposed methods and metrics on an example involving personnel movement inside a simplified ship. The study presented is an extension of the one originally presented in Kana and Singer⁵ and presented at the PRADS’2016 conference. The original work examined the eigenvalues as a means to quantify changes in decision-making behavior as individuals egress. This article, on the other hand, examines the principal eigenvectors as a metric to study probabilistically where individuals converge to on the vessel based on their decisions. While the case setup remains the same, the specific eigenvector methods, and derived metrics, are unique. The case study was kept the same to highlight the physical relationship between the principal eigenvectors and the eigenvalues. Using the same case study, some of the qualitative conclusions made in Kana and Singer⁵ can be quantified.

Model assumptions

A simple vessel layout is presented in Table 1 where each cell represents a different room of the vessel. The entries denote the labeling convention for each room (e.g. the bottom left room is labeled (1,1)). The solid black state is an inaccessible area. For this study, the rooms are not labeled for a specific use. Although these rooms may already be classed as galley, engine room, and so on, this information is not used in this model, only the information regarding the accessibility of the room. This case study aims to understand the implications of decisions individuals make during an emergency with respect to the connectivity of rooms throughout the ship. It is recognized that this is a simple layout, but by preserving the layout with respect to earlier studies it is possible to draw quantitative conclusions from the previous work.

Table 1.

Eleven-room vessel layout.

The entries include the labeling convention of the rooms. The fire starts in room (2,4) and the exit is room (3,4).

To simulate an emergency, assume a fire has broken out in room (2,4), and individuals need to move about to find the exit, located at (3,4). There is uncertainty in their movements to simulate the confusion associated with an emergency. For instance, individuals may panic, smoke may be blocking their visibility, or the ship’s motions may discomfort people moving through the vessel. The location of the individuals is given by the state vector defined in equation (9)

s = (s_{1, 1}, s_{1, 2}, s_{1, 3}, s_{1, 4}, s_{2, 1}, s_{2, 2}, s_{2, 3}, s_{2, 4}, s_{3, 1}, s_{3, 2}, s_{3, 3}, s_{3, 4})

(9)

Each element in the vector gives the probability that an individual is located in a given room. For instance, if $s_{1, 1} = 0.5$ , then there is a 50% probability that the individual is located in the lower left room (1,1). The sum of all elements in the vector must equal 1. Due to the properties of the proposed method, the initial location of the individual will have no effect on where they converge in the long term.

MDP model

This section outlines how the states, actions, transition probabilities, and rewards of the SC-MDP model are defined for this specific study. It is assumed that the transition probabilities and rewards do not change with time. A finite horizon MDP is run for 30 decision epochs. This is selected to allow individuals to take up to 30 steps to maximize their expected utility.

States

The states are defined as the individual rooms in the ship, as presented in Table 1.

Actions

The individuals may move one step at each decision epoch. They may move up, down, left, or right.

Transition probabilities

The probability of moving in the direction desired varies for each simulation. For instance, during one situation there is only 0.9 probability of moving in the desired direction, while there is a 0.05 probability of moving in either direction laterally to the desired one. For this situation, the transition probability is defined as $p = 0.9$ . This probability is varied in the study. If an individual steps directly into a wall, then they remain in the same room.

Rewards

A utility function is used to simulate the pain the person experiences the longer they are in the ship looking for the exit. The person’s objective is to minimize their pain while heading toward the exit. To do this, they aim to maximize their cumulative reward after a given number of steps. The SC-MDP model will be used to determine their best sequence of decisions given the specific uncertainty and rewards, as well as their expected value.

Individuals receive a reward for landing in a given state, and those rewards are given in Table 2. The room with the $r = - 1$ reward is designed to simulate the room with a fire, while the room with the $r = + 1$ reward is designed to simulate the exit room. Sensitivity studies are performed on the $r = - 0.04$ rewards; however, the $r = + 1$ and $r = - 1$ rewards remain fixed.

Table 2.

The initial rewards the individuals receive for landing in a given state.

This study varies the −0.04 rewards, while the +1 and −1 rewards remain fixed.

Results

A standard MDP provides the best decision paths an individual should follow as it minimizes the pain while taking into account all the assumptions of the model. Presented in Table 3 is the best decision paths for a reward of $r = - 0.04$ and a uncertainty of $p = 0.9$ . These decisions are unique only to the given rewards and uncertainty, as the decisions are sensitive to both the uncertainty and rewards. Kana and Singer⁵ studied the variations in these decision paths using a decision metric they defined as the ratio between the largest eigenvalue and the magnitude of the second largest eigenvalue. They did this in an attempt to quantify the effect changes in local decisions may have on the system as a whole.

Table 3.

Best decision paths for $p = 0.9$ and $r = - 0.04$ .

Applying the methods discussed above, this article uses the principal eigenvector to represent the steady-state distribution of the crew following the prescribed decision paths. Four analyses were performed using the eigenvector to examine the relationship the uncertainty, the rewards, and the passageways have on the stable distribution of the individuals in the vessel. First, a sweep of both the uncertainty and rewards was performed simultaneously to see the percentage of individuals who will make it to the exit room (3,4) in the long run. The next two studies looked at a sweep of the rewards and a sweep of the uncertainty individually to examine both the total distribution of individuals in vessel and the magnitude of the changes in distributions based on the changes in the uncertainty and rewards. The final study varied the layout by blocking access between rooms (1,3) and (2,3), which effectively blocks the passageway between the fire and the inaccessible area. This last study aims to show how design implications can be studied using this method.

A study varying both the uncertainty and the rewards

A sweep of the uncertainty and rewards was performed to test the impact these parameters have on the percentage of individuals who make it to the final exit state in the long run. The uncertainty was varied from $0 < p < 1$ and the rewards were varied from $- 2.0 < r < 0$ . Figure 3 shows the probability that an individual will successfully make it to the exit room (3,4) in the long term. This was done by looking at element $s_{3, 4}$ in the principal eigenvector.

Figure 3.

Probability an individual arrives at the exit room (state (3,4)) in the long run based on a variation in uncertainties and rewards.

This figure represents various types of situations and different behaviors that may occur in vessels. For instances, when there is dense, harmful smoke, possibly from a fire, there is high uncertainty in the movement along with high pain that may reduce the “rewards” of the individual. This case is seen in the bottom left-hand corner in Figure 3. There may also be situations where there is harmful smoke, but no sight impairment, such as a gas leak (see top left of figure). An evacuation drill is an example of the top right scenario where there is no uncertainty in the movement, nor pain that is experienced. The bottom right-hand corner can describe a situation such as fog, or a ship in heavy seas where there is high uncertainty in movement, but there is no pain experienced, thus reducing the desire to head toward the exit. These different situations cause different behavior, and thus affect the probability that an individual will arrive at the exit point.

Examining Figure 3 as a whole, it is clear that the probability of landing in the exit room is more sensitive to the uncertainty than it is to the rewards. As the probability of moving in the desired direction increases, the probability of an individual making it to the exit gradually increases as well. Below $p = 0.3$ , the probability of making it to the exit remains steady at 33% for the majority of the rewards. When the reward approaches 0 $(r \to 0^{-})$ , a step change occurs and the probability decreases drastically to 25%. Above $p = 0.3$ , the probability gradually increases until $p = 1$ , in which case 100% of individuals make it safely to the safe exit room.

Varying the rewards has little effect on the results. For most of the range of the rewards tested, the percent of individuals remains mostly unchanged as the rewards change. The one noticeable sensitivity happens as a step function near $r = 0$ . As the rewards increase, at some point slightly before $r = 0$ , the probability that an individual will make it to the safe room reduces drastically. This change starts close to $r = 0$ for $p = 1$ and slowly moves toward more negative rewards as p is reduced. Below $p = 0.5$ , the step begins to happen much farther away from $r = 0$ . The step is significant for $0.5 < p < 1$ because it is the same significant bifurcation line that was identified by Kana and Singer⁵ using the decision metric. They identified this bifurcation happens when the decision in room (2,3) changes from “up” to “left.” They were able to justify the importance of this qualitatively. By deciding to go “left,” this decision path effectively blocks off the route between the inaccessible area (2,2) and the room with the fire (2,4). This forces individuals to travel clockwise around room (2,2) as opposed to taking the shorter route. By examining the principal eigenvectors, it is clear this change also has a significant effect on the probability an individual will eventually make it to the exit room. Thus, spectral analysis has been able to identify this transition region as one of significant importance using both eigenvalue analysis with the decision metric and principal eigenvector analysis through steady-state analysis.

A study varying only the rewards

A sweep of the rewards from $- 2 < r < 0$ was performed for $p = 0.8$ . As can be seen in Table 4, four different steady-state distributions exist for this range of rewards. For the most negative rewards, there is nearly an 88% chance an individual will make it to the final exit state (3,4), while there is nearly an 11% chance they end up in the room with the fire (2,4). There is a 1% chance an individual will end up congregating in the passage near the room with the fire (room 2,3). As the reward is adjusted to $- 1.65 < r \leq - 1.44$ , the probability of an individual ending up long term in the room with the fire decreases to less than 10%, while the probability of finding the safe exit remains nearly the same at close to 88%.

Table 4.

Steady-state distributions as calculated by the dominant eigenvector for $p = 0.8$ .

The values indicate the long-term probabilistic location of the individuals in the vessel.

As soon as the reward changes above −1.44 for the range $- 1.44 < r \leq - 0.03$ , there are clear changes. The probability of the individuals congregating long term in the room with the fire decreases to nearly 0. However, now more than 10% will end up in the room just outside the safe exit (3,3). One of the assumptions in this model is that an individual must make a decision to move in a given direction at each decision epoch, even if they have reached the safe state. The change in the steady-state distribution here is due to the change in underlying decision in the (3,4) room. For $- 1.65 < r \leq - 1.44$ , the best decision while in the safe state is to move “right,” meaning 10% of the time individuals will accidentally step into the room with the fire. For $- 1.44 < r \leq - 0.03$ , the best decision changes to “up,” which means that individuals take a misstep outside of the safe room to state (3,3). This assumption could model situations where there is panic and individuals may move out of the safe room even after they have already landed there. This causes the change in distributions between state (2,4) and state (3,3) for a reward of $r = - 1.44$ . Again, the percentage of those in the safe exit room remains just less than 88%. The previous study that performed a sensitivity study on both the uncertainty and rewards was unable to discern the two transition regions at $r = - 1.65$ and $r = - 1.44$ because it focused only on the impact on room (3,4) and missed the impact on the other rooms.

The final change happens when the rewards are increased to greater than −0.03. The percent in the safe exit is now less than 81%, while there is a 0% chance someone will end up long term in the room with the fire. Roughly 5% will remain immediately adjacent to the fire room (2,3). A noticeable change also happens for the states far away from the fire and safe exit states, where in each state there is just less than a 1% chance that someone will end up there. This change happens at the same transition region identified by the change in the decision metric as discussed by Kana and Singer.⁵ This last region simulates a situation where the pain from the smoke is minimal and there is a small chance someone may prefer just to stay far away from the fire, as opposed to heading for the exit and risking the chance of ending up in the fire room.

This first eigenvector metric measured only the distributions of individuals, while this next metric quantifies the impact of these changes by looking at the magnitude of the angle formed between the eigenvector of the previous distribution and that of the new distribution. The magnitude of the angles between the two principal eigenvectors (one from the previous set of decisions and one from the new set of decisions) is given in Table 5 and Figure 4. In the figure, the magnitude of the angles is displayed against a neutral axis. Displaying these angles graphically has the benefit of visually showing a vast number of angles that may get confusing in a table alone. This will become clear in the next section where there are numerous sets of decisions and thus multiple angles to display.

Table 5.

The magnitude of the angles between the principal eigenvectors for given rewards and $p = 0.8$ .

Reward, r	$\| θ_{\deg} \|$
−1.65	0.9
−1.44	8.9
−0.03	3.2

The rewards indicate the transition regions where the steady-state distribution changes.

Figure 4.

Visual display of the magnitude of the angles between the eigenvectors for given rewards and $p = 0.8$ . The rewards indicate the transition regions where the steady-state distribution changes.

By examining the angles, it is evident that the change in steady-state distributions that occurs at $r = - 1.65$ is indeed small. The two distributions are only 0.9° different. This is opposed to the significant change at $r = - 1.44$ , which is nearly 9°. This change is significant even though it does not appear in Figure 3, which examined only the final exit state. Thus, this is an instance when examining all states is important, otherwise the decision-maker may miss an important transition region if there is too strong a focus on a single state. The change at $r = - 0.03$ is less significant than the one at $r = - 1.44$ , accounting for only a magnitude of 3.2°.

A study varying only the uncertainty

This study examined a sweep of uncertainties between $0.6 < p < 1$ for $r = - 0.1$ . The results are markedly different than those from varying the rewards. Here, with each small change in the uncertainty comes a small change in the distribution of individuals in the vessel. Thus, there are no clear significant bifurcation regions, but instead a gradual change. The stable distributions in increments of $p = 0.1$ are presented in Table 6.

Table 6.

Steady-state distributions as calculated by the principal eigenvector for $r = - 0.1$ .

The values indicate the long-term probabilistic location of the individuals in the vessel.

As the probability of moving in the desired direction, p, increases, the probability of landing in the safe exit state gradually increases as well. For $p = 0.6$ , there is more than a 70% chance an individual will make it to the safe room, while that percentage increases to a full 100% for $p = 1.0$ . The long-term chance of landing in the room with the fire is 1.5% for $p = 0.6$ and decreases to 0% by $p = 0.9$ . The states just outside the fire and safe exits also have decreasing probabilities with increasing p.

This study also examined the magnitude of these incremental changes using the magnitude of the angle formed between the eigenvectors. Table 7 shows the angles formed incrementally for each $p = 0.05$ for $0.6 < p \leq 1$ . The angles are all small, less than 0.7°, and are decreasing with increasing p. For $p = 0.61$ , the angle is 0.69°, while for $p = 1.0$ , the angle is much less at 0.29°. Due to the more continuous nature of this progression, visualizing these angles is beneficial. Figure 5 shows numerous small changes from $p = 0.61$ to $p = 1$ . It can be seen that not only does the angle get smaller but also the rate at which the angle gets smaller is decreased. That is, the distributions begin to approach $p = 1$ more slowly due to their ever decreasing incremental change.

Table 7.

The magnitude of the angles between the eigenvectors for given probability of moving in the desired direction, p, and $r = - 0.1$ .

Probability of moving in desired direction, p	$\| θ_{\deg} \|$
0.61	0.69
0.65	0.62
0.70	0.55
0.75	0.49
0.80	0.44
0.85	0.40
0.90	0.36
0.95	0.32
1.0	0.29

Figure 5.

Visual display of the magnitude of the angles between the eigenvectors for given probability of moving in the desired direction, p, and $r = 0.1$ .

In all cases, this change is gradual and follows a more continuous trend. This behavior is different to the step function nature that was present when varying the rewards. This is logical based on the shape of Figure 3 where the gradient was more pronounced by varying the uncertainty as opposed to the rewards. Thus, it is clearly shown that the variations in the uncertainty interact with the decisions in a different manner than the variations in the rewards.

A study varying the layout of the vessel

The final study examines varying the layout of the vessel to show how this method may be used to explore design decisions related to ship layouts. For this study, the layout is changed so that the passage between state (1,3) and (2,3) is fully blocked. To do this, the probability of transitioning between these two states was set to 0. This may simulate placing a wall there, the installation of a fire door between compartments, or the presence of some other blockage that limits movements between those rooms. This variation in the layout was selected to test the result that when the decision in room (2,3) changes from “up” to “left,” it effectively blocks this passageway. This study will test to see how this blockage may change the probability of individuals who make it to the exit.

First, the decision paths were examined to show how this blockage would affect personnel movement. As can be seen in Table 8, for $p = 0.8$ and $r = - 0.04$ , the decisions do change, as is expected. The decisions for states (1,2), (1,3), and (1,4) are changed as now the best decision is to move either clockwise around state (2,2) or actually go through the room with the fire en route to the safe exit state.

Table 8.

Best decision paths for $p = 0.8$ and $r = - 0.04$ for the original layout (left) and the layout with the blockage (right).

The double line signifies the location of the blocked passageway.

Despite these different decision paths, the analysis of the principal eigenvectors showed that these had very little effect on the probability one would make it to the exit state (Figure 6). Note the similarities between Figures 3 and 6, which represented the original layout. For the majority of the scenarios varying the uncertainty and the rewards, the results are markedly similar. The primary difference that is visible involves the slight change in the bifurcation line close to $r = 0$ . This shows that for this layout, blocking the passageway has almost the same effect as when the decision in state (2,3) moves from “up” to “left.”

Figure 6.

Probability an individual arrives at the exit room (state (3,4)) when the passage between rooms (1,3) and (2,3) is blocked.

The full distribution of individuals was measured to see the comparison between the two layouts. For this analysis, the probability of moving in the desired direction was set at $p = 0.8$ , while three different rewards were tested: $r = - 0.4$ , $r = - 0.025$ , and $r = - 0.001$ . These locations were selected to test a region to the left of the bifurcation line, a location that is in the middle of the old bifurcation line and the new one, and one that is to the right of the bifurcation line. As shown in Table 9, the distribution of individuals is unchanged between layouts for $r = - 0.4$ , which is to the left of the bifurcation line. For $r = - 0.025$ , the original layout shows a smaller probability of individuals making it to the exit. Meanwhile, the layout with the blocked passageway shows the same distribution as for $r = - 0.4$ . For the area to the right of the bifurcation line ( $r = - 0.001$ ), the layout with the blocked passageway shows that there are only three rooms where individuals are likely to congregate. This compared to the original layout, where individuals may be more dispersed throughout the vessel.

Table 9.

The distribution of people throughout the layout for three different rewards and $p = 0.8$ .

To calculate the differences between the distributions for these two different layouts, the angle between these eigenvectors was calculated (Table 10). As mentioned, the distributions for $r = - 0.4$ are identical, resulting in an angle of 0°. However, for the two other locations tested, the change is calculated to be just more than 3°. This shows that for this case study, blocking the passageway only affects the distribution of individuals when the pain experienced is low.

Table 10.

The angles between the principal eigenvectors between the original layout and the one with the blocked passageway for $p = 0.8$ .

Reward, r	$\| θ_{\deg} \|$
−0.4	0.0
−0.025	3.2
−0.001	3.5

Based on the results from the layout study, two conclusions can be drawn. First, the change in layout has a modest effect on the behavior of people and their eventual distribution throughout the layout. The proposed method provides new insight to study these design changes and there consequences on the egress performance of a given layout. Second, this analysis supports the claim made by Kana and Singer⁵ that the policy of moving left in state (2,3) essentially closes the passage between states (1,3) and (2,3), thus forcing people to move clockwise around state (2,2).

Discussion

The following points are worthy of discussion:

This case study was designed to highlight the benefit of the methods proposed as applied to studying evacuation patterns, and specific conclusions regarding the layout itself should not be extended for other layouts. For instance, for this case study, blocking the passageway showed to have only modest impacts; however, for a different layout, the results could be different.

These methods provide leading indicator insights into personnel movement without the need for detailed knowledge regarding the vessel layout, full multi-agent simulations, or complete time domain simulations. The case study presented focused on how people egress, understanding the decisions they make under uncertainty, and the interaction between the individuals themselves and the layout of the vessel taking into account limited details about the individuals and the vessel layout.

The case study highlighted the importance of including uncertainty in egress modeling. Deterministic models may be unable to account for situations where movement may be uncertain due to panic or poor visibility. Failure to account for this uncertainty may lead to incomplete or even conflicting answers.

This method handles various situations simultaneously. There is no need to know initial distribution of individuals, nor how the spaces are designated. Eigenvector analysis applied to the SC-MDP model enables the ability to examine all states at once and is able to relay their relative significance during decision changes. Understanding how individuals interact with the vessel is key to designing layouts that facilitate fast evacuations.

Conclusion

A method for estimating evacuation patterns during early stages of design has been presented that involves applying principal eigenvector analysis to the SC-MDP model. The principal eigenvector was examined as a leading indicator metric for measuring where individuals may congregate on board a vessel during times of evacuation. A case study was presented involving evacuation patterns and personnel movement in a simplified vessel layout. A set of sensitivity studies showed that uncertainty in an individual’s movement had a larger effect on where they would end up as opposed to the pain they were experiencing. Another study showed that blocking a passageway had a similar effect on the individual’s location as when a specific movement decision is made.

Future work

The authors have identified several areas for future work to help improve the fidelity of the proposed method. The future work is split between (1) connecting this model to more representative vessel layouts and (2) better predicting the uncertainty and reward functions for the model. The layout presented is limited in its current form, and the authors would like to extend that to include layouts that better represent modern vessels. This may include both increasing the size and scope of the layout and including the functionality of the rooms as additional information for the model to use. Also, this study used uncertainty and reward functions which were only loosely based on physiological behavior. To better predict the uncertainty or the reward functions, future studies could look into implementing research studies aimed at understanding the relationship between humans and their immediate environment. Such studies may include Duarte et al.,¹⁹ Vilar et al.,²⁰ or Ahola and Mugge,²¹ who aim to relate attributes of a given environment to how individuals may move or behave. The results from these studies could help improve the fidelity of the uncertainties in this method or help tailor the method to one specific case study. Both these areas will help build upon the theoretical foundations presented in this article to more applied scenarios readily accessible for practicing ship designers.

Footnotes

Acknowledgements

The authors would like to thank Ms Kelly Cooper and the U.S. Office of Naval Research for their support of this research.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

IMO. Guidelines for evacuation analysis for new and existing passenger ships, 2007, www.imo.org

Germanischer Lloyd. Preliminary guidelines for safe return to port capability of passenger ships. Annex A: report. Hamburg: Germanischer Lloyd, 2009.

Gillespie

Singer

DJ.

Generating functional complex-based ship arrangements using network partitioning and community preferences. Ocean Eng 2013; 72: 107–115.

Van Oers

Hopman

. Simpler and faster: a 2.5 D packing-based approach for early stage ship design. In: Proceedings of the eleventh international marine design conference IMDC2012, Glasgow, UK.

Kana

Singer

. A ship egress analysis method using spectral Markov decision processes. In: Proceedings of the 13th international symposium on practical design of ships and other floating structures (PRADS’2016), Copenhagen, 4–8 September 2016.

Ahola

Murto

Kujala

. Perceiving safety in passenger ships: user studies in an authentic environment. Saf Sci 2014; 70: 222–232.

McKenna

Costa Concordia: last victim found in wreckage. The Telegraph, 3 November 2014. http://www.telegraph.co.uk/news/worldnews/europe/italy/11205374/Costa-Concordia-body-of-final-victim-found-on-board.html

Andrews

Casarosa

Pawling

. Integrating personnel movement simulation into preliminary ship design. In: Proceedings of the RINA international conference on human factors in ship design, London, March 2007, pp.117–128. Royal Institution of Naval Architects.

Guarin

Hifi

Vassalos

Passenger ship evacuation: design and verification. In: Shumaker

Lackey

(eds) Virtual, augmented and mixed reality: applications of virtual and augmented reality (vol. 8526). Berlin: Springer, 2014, pp.354–365.

10.

Cho

Park

KP.

Velocity-based egress model for the analysis of evacuation process on passenger ships. J Mar Sci Technol 2016; 24(3): 466–483.

11.

Rigterink

Piks

Singer

DJ.

The use of network theory to model disparate ship design information. Int J Nav Arch Ocean 2014; 2014; 6: 484–495.

12.

Niese

Singer

DJ.

Strategic life cycle decision-making for the management of complex systems subject to uncertain environmental policy. Ocean Eng 2013; 72: 365–374.

13.

Niese

ND.

Life cycle evaluation under uncertain environmental policies using a ship-centric Markov decision process framework. PhD Thesis, University of Michigan, Ann Arbor, MI, 2012.

14.

Anton

Rorres

Elementary linear algebra: applications version. 9th ed.Hoboken, NJ: John Wiley & Sons, 2005.

15.

Sheskin

TJ.

Markov chains and decision processes for engineers and managers. New York: CRC Press, 2011.

16.

Russell

Norvig

Artificial intelligence: a modern approach. 2nd ed.Upper Saddle River, NJ: Prentice Hall, 2003.

17.

Kirkland

Subdominant eigenvalues for stochastic matrices with given column sums. Electron J Linear Algebra 2009; 18: 784–800.

18.

Kana

AA.

Forecasting design and decision paths in ship design using the ship-centric Markov decision process model. Ocean Eng 2017; 137: 328–337.

19.

Duarte

Vilar

Rebelo

. Some evidences of the impact of environment’s design features in routes selection in virtual environments. In: Shumaker

(ed.) Virtual and mixed reality: new trends (VMR 2011, lecture notes in computer science, vol. 6773). Berlin; Heidelberg: Springer, 2011, pp.154–163.

20.

Vilar

Rebelo

Noriega

. The influence of environmental features on route selection in an emergency situation. Appl Ergon 2013; 44: 618–627.

21.

Ahola

Mugge

Safety in passenger ships: the influence of environmental design characteristics on people’s perceptions of safety. Appl Ergon 2017; 59(Part A): 143–152.