Social Hybrid Reciprocal Velocity Obstacle-Based Socially Aware Mobile Robot Navigation Framework

Abstract

In this paper, we propose a social hybrid reciprocal velocity obstacle (SHRVO)-based navigation framework which allows a mobile robot to avoid safely and socially humans or groups of humans in dynamic social environments. The integration of social behaviors, including passing to the right of humans or human groups and selecting the left to overtake, into the original hybrid reciprocal velocity obstacle algorithm is the key idea of our proposed framework. The developed frame work is evaluated by conducting a sequence of experiments in simulation environment. The experimental results have demonstrated the success of the proposed framework in safely navigating a mobile robot in dynamic social environment while still adhering to the social manners.

1 Introduction

Recently, many socially aware navigation frameworks [7, 13] and [1] have been presented to address the problem of navigating mobile robots autonomously in public environments such as museums, airports, commercial centers and urban areas. Depending on how to integrate the human information and social restraints into the navigation systems, these current humanly aware systems can be relatively separated into: (i) social costmap-based approaches and (ii) motion planning system-based approaches. While the methods in the first category incorporate the human data and social behaviors to build the costmap function, the techniques in the second category directly integrate the social restriction into the motion planning systems.

Several navigation systems for mobile robots [6, 9, 10] and [18] have been introduced based on the social costmap techniques in recent times. In these systems, the 2-D Gaussian and linear techniques are applied to combine the human information and social constraints with the aim of building the social costmap. After that, the path planning algorithms [4, 16] and dynamic window approach [3] are utilized to generate a feasible trajectory and a motion command to drive the robots to their targets. When these techniques are installed, the robots not only can avoid safely the surrounding humans, but also behave socially such as ensuring no violation of private space and social interaction area and selecting a appreciate side to overtake a person. However, when operating in crowded and dynamic environments [9] and [8], the computation process of these methods to determine a feasible path for mobile robots is very complicated and takes a lot of time.

In term of approaches based on motion planning system, the recent proposed navigation frameworks [2, 14, 17] and [12] have been developed by incorporating the information of human into the conventional motion planning algorithms, for instance social force model [5] and velocity obstacles [15]. The computation time to generate the optimal path for mobile robots has been significantly improved and these techniques also have been verified in real-world environments. However, the social constraints such as taking the right side to pass and selecting the left to overtake are not considered in these systems.

In this paper, a human-like navigation system for mobile robots is proposed by incorporating the social rules into the original hybrid reciprocal velocity obstacle (HRVO) approach [15], which is a real-time algorithm considering the cooperation between robots operating in the shared environments. Particularly, we incorporate the social behaviors including selecting the right side to pass a human or a human group and taking the left side when overtaking, into the HRVO model, and propose a social hybrid reciprocal velocity obstacle (SHRVO) model. When equipped the proposed SHRVO model, the mobile robots are capable of behaving humanly when avoiding humans and human groups, and navigating safely towards their targets.

The remainder of the paper is arranged as follows. Section 2 introduces the proposed social hybrid reciprocal velocity obstacle model. The simulation experiments are presented in Sect. 3. The conclusion of the paper is provided in Sect. 4.

2 Proposed Framework

2.1 Problem Description

Considering a socially dynamic environment which consists of a mobile robot and N surrounding humans. The mobile robot has a fixed radius $r_{A}$, a current position $p_{A}$, an actual velocity $\mathbf{v} _{A}$, a goal situated at $p_{A}^{goal}$ and a preferred speed $p_{A}^{pref}$. The goal can be directly selected as a fixed position in the plane or be the consequence of some algorithms, for instance global planning or scheduling algorithms. The preferred speed is identified as the speed taken by the robot when there are no humans or obstacles in its path. Similar to choosing the goal of the mobile robot, this speed can be pre-selected or be the output of some external methods. In addition, humans presenting around the robot can be denoted as $\mathbf{P} =\lbrace \mathbf{p} _1, \mathbf{p} _2,..., \mathbf{p} _N \rbrace$, where $\mathbf{p} _i$ is the $i^{th}$ person. Each human also has a constant radius $r_{i}$, a current position $p_{i}$, an actual velocity $\mathbf{v} _{i}$, a goal situated at $p_{i}^{goal}$ and a preferred speed $p_{i}^{pref}$.

The objective of the mobile robot is to independently and concurrently compute a new velocity at each time step to generate an optimal trajectory towards its desired destination while not only ensuring the collision-free and oscillation-free with any human or obstacle in the environment but also following the social rules such as overtaking to the left of a human or a human group and passing them on the right side.

Fig. 1.

(a) The configuration of HRVO. (b) The construction of the combined hybrid reciprocal velocity obstacle for the dark robot.

2.2 Hybrid Reciprocal Velocity Obstacle Model

The hybrid reciprocal velocity obstacle concept [15] is a real-time navigation algorithm for multiple mobile robots or virtual agents in which the reciprocity between robots is specially considered. The hybrid reciprocal velocity obstacle was developed to resolve one of the particular limitations of the reciprocal velocity obstacle formulation which is known as “reciprocal dance”, and this algorithm has been successfully applied to mobile robots in an real-world environment. A brief review of the concept of the hybrid reciprocal velocity obstacle will be described in this section.

To counter the situation of “reciprocal dances”, the hybrid reciprocal velocity obstacle combines the velocity obstacle and the reciprocal velocity obstacle to discourage robots from passing each other on different sides. For two robots A and B, if $\mathbf{v} _{A}$ is to the right of the centerline of the reciprocal velocity obstacle for robot A induced by robot B ($\mathbf{RVO} _{A|B}$), with the aim of encouraging robot A to pass on the right side of robot B, the reciprocal velocity obstacle will be expanded to the left side by replacing the left edge of $\mathbf{RVO} _{A|B}$ with the left edge of the velocity obstacle $\mathbf{VO} _{A|B}$. The intersection point between the right side of $\mathbf{RVO} _{A|B}$ and the left side of $\mathbf{VO} _{A|B}$ will be the apex of the hybrid reciprocal velocity obstacle. We exchange right and left and mirror the procedure if $\mathbf{v} _{A}$ is to the left of the centerline. The geometric interpretation of constructing a hybrid reciprocal velocity obstacle $\mathbf{HRVO} _{A|B}$ for robot A induced by robot B is shown in Fig. 1(a).

In stead of having only two robots A and B, we assume that there is a set of robots $\mathbf{A}$ operating together in an environment with a set of obstacles $\mathbf{O}$. Each robot $A_{i}$ in $\mathbf{A}$ has a current position $p_{Ai}$, velocity $\mathbf{v} _{Ai}$, radius $r_{Ai}$ and goal position $p_{Ai}^{goal}$ that can be recognized or measured by other robots. Each robot A$_{i}$ also has a preferred velocity $\mathbf{v} _{Ai}^{pref}$ toward its goal (velocity that a robot takes when there are no other robots or obstacles in its path) which is defined as follow:

(1)

Each robot A$_{i}$ will independently execute a continuous cycle including: (i) Sense positions and velocities of nearby robots; (ii) Select optimal new velocity outside union of HRVO’s; (iii) Compute control input from new velocity; (iv) and Apply control input to robot’s actuators until reaching its goal position.

Based on information from the sensing phase, the hybrid reciprocal velocity obstacles HRVO induced by each neighboring robot in $\mathbf{A}$ and the velocity obstacles VO generated by each obstacle in $\mathbf{O}$ for robot A$_{i}$ will be constructed and then unified to form the combined hybrid reciprocal velocity obstacle.

$$\begin{aligned} \mathbf{HRVO} _{Ai} = \bigcup _{Aj\in \mathbf{A} } HRVO_{Ai|Aj} \cup \bigcup _{Oj \in \mathbf{O} } VO_{Ai|Oj} \end{aligned}$$

(2)

Because the data that are obtained from sensors and used for calculating the hybrid reciprocal velocity obstacle contain uncertainty, the combined uncertainty-adjusted hybrid reciprocal velocity obstacle will be constructed to ensure the correct functioning of HRVO approach by applying a Kalman filter.

For collision avoidance, the robot A$_{i}$ should select a new velocity $\mathbf{v} _{Ai}^{new}$ that is closest to its preferred velocity $\mathbf{v} _{Ai}^{pref}$ and outside the combined uncertainty-adjusted hybrid reciprocal velocity obstacle:

$$\begin{aligned} \mathbf{v} _{Ai}^{new} = arg\min _{v \notin \mathbf{HRVO} _{Ai} } \Vert \mathbf{v} -\mathbf{v} _{Ai}^{pref}\Vert 2 \end{aligned}$$

(3)

The ClearPath efficient geometric algorithm is used to compute this velocity. Due to the kinematic restrictions of the robot, the velocity $\mathbf{v} _{Ai}^{new}$ will be transformed into a control input (wheel speeds $v_{l}$ and $v_{r}$) to allow the robot quickly reach the $\mathbf{v} _{Ai}^{new}$. This cycle will be continued until the robot reaches its goal position. This is illustrated in Fig. 1(b).

Algorithm 1 describes overall approach for navigating multiple mobile robots by applying the concept of HRVO, which is divided into three primary steps: (i) perception (Lines 3–4 of the Algorithm 1), construction (Lines 5–11 of the Algorithm 1), and (iii) selection (Lines 5–1 of the Algorithm 1). The input of the Algorithm 1 is the set of robots $\mathbf{A}$ and set of obstacles $\mathbf{O}$, and the output is the control input wheel speeds $\mathbf{v} _r$,$\mathbf{v} _l$ of the mobile robot. The first step is perception and in which each robot in $\mathbf{A}$ acquires its own position and velocity, and those of the surrounding robots and obstacles in $\mathbf{O}$. Because sensors contain uncertainty, a Kalman filter is used to obtain the accurate estimation of the positions and velocities of the robots and obstacles by providing a Gaussian distribution of these information. In the second step, the velocity obstacles VO and reciprocal velocity obstacles RVO for each robot in $\mathbf{A}$ induced by other surrounding robots in $\mathbf{A}$ and velocity obstacles in $\mathbf{O}$ are constructed. Next, depending on the relative position between the centerline of RVO and the velocity of the robot, one of two edges of RVO will be replaced with a corresponding edge of VO to construct the hybrid reciprocal velocity obstacle HRVO. After that, the HRVO will be expanded to the uncertainty-adjusted hybrid reciprocal velocity obstacle HRVO$^{*}$ by using the Gaussian distribution to reduce the uncertainty in the perception step. The velocity obstacle VO$_{A|O}$ for each obstacle in $\mathbf{O}$ in the environment are also transferred to uncertainty-adjusted velocity obstacle VO$^{*}$. The last part of this step will be the construction of the combined uncertainty-adjusted hybrid reciprocal velocity obstacle for each robot in $\mathbf{A}$. In the final selection step, a new velocity for each robot will be computed by using the Clearpath algorithm before converting to the speeds of the wheels which are the control input of each robot.

2.3 Proposed Social Hybrid Reciprocal Velocity Obstacle Algorithm

In HRVO concept, for two robots A and B, whether robot A will choose a new velocity to the right or left of $\mathbf{RVO} _{A|B}$ depending on the relative position between $\mathbf{v} _{A}$ and the centerline of $\mathbf{RVO} _{A|B}$. In our social HRVO concept, in addition to relative position, we also consider the distance between the current velocity of robot A and the centerline of $\mathbf{RVO} _{A|B}$ when choosing the new velocity for robot A. We install a number that plays a role as a threshold for this selection. If the distance between the velocity and centerline of $\mathbf{RVO} _{A|B}$ is larger than the threshold, robot will follow the HRVO concept for choosing new velocity (Lines 14–17 of the Algorithm 2). If the distance is smaller than the threshold and the velocity is not to the side as we wish, the centerline of $\mathbf{RVO} _{A|B}$ will be moved an equal distance to the threshold and to the side that we do not wish the robot A to pass (Lines 10–13 of the Algorithm 2). This transfer ensures that $\mathbf{v} _{A}$ is to the desired side of the centerline of $\mathbf{RVO} _{A|B}$. By the symmetry, this is totally similar to robot B. Consequently, robots can pass others on the side that is in accordance with social rules. Because of adding the social rules to the HRVO concept, we call the result a social hybrid reciprocal velocity obstacle, and denote it $\mathbf{SHRVO} _{A|B}$. The method to construct the social hybrid reciprocal velocity obstacle is described specifically in Algorithm 3. The input of Algorithm 3 includes the radius, position, current velocity and preferred velocity of all robots in the environment, while the output will be the construction of social hybrid reciprocal velocity obstacle consisting of apex, left side and right side. The Algorithm 3 first calculates the parameters that will be used to create the VO, RVO and declares a threshold as a condition for constructing the SHRVO (Lines 4–9 of the Algorithm 3). If the velocity of robot is to the right (or left) of the centerline of the RVO but the distance between them is less than the threshold, the SHRVO will be generated to make the robot act like human in society (Lines 10–14 of the Algorithm 3). If this distance is larger than the threshold, the robot will follow the concept of HRVO (Lines 10–14 of the Algorithm 3).

Fig. 2.

The first figure is the geometric interpretation of R-SHRVO for the right rule and the second is the geometric interpretation of R-SHRVO for the left rule

The geometric interpretation of R-SHRVO for the right rule is illustrated in Fig. 2(a). Because the distance between v$_{A}$ and CL is smaller than the threshold b, robot A will choose a new velocity to the right of RVO$_{A|B}$ even though v$_{A}$ is to the left of the centerline of RVO$_{A|B}$. To encourage this, a right social HRVO is created by enlarging the reciprocal velocity obstacle to the left side. The steps are as follows:

Step 1 - Create a new velocity obstacle (VO$^\prime$): From the apex of VO ($\mathbf{v} _{B}$), draw a vector $\mathbf{v} _{b}$ that is parallel to the Ox axis (origin of the coordinated axis is at the center of robot A), toward the left and has a length of threshold b.

$$\begin{aligned} \mathbf{v} _{b} = \mathbf{v} _{B} -(b,0) \end{aligned}$$

(4)

Project $\mathbf{v} _{b}$ onto velocity $\mathbf{v} _{B}$, we get point B$^\prime$. This is the new apex of VO$^\prime _{A|B}$. And from this apex, draw two edges that are parallel to the edges of $\mathbf{VO} _{A|B}$ to form a new velocity obstacle $\mathbf{VO} ^\prime _{A|B}$.

Step 2 - Create a SHRVO for right rule (R-SHRVO): The apex of R-SHRVO is the intersection between the right side of $\mathbf{RVO} _{A|B}$ and the left side of $\mathbf{VO} ^\prime _{A|B}$.

$$\begin{aligned} \mathbf{apex} = \text{ right } \mathbf{RVO} _{A|B} \cap \text{ left } \mathbf{VO} ^\prime _{A|B} \end{aligned}$$

(5)

As a result, the left boundary of SHRVO for right rule will be the left side of VO$^\prime _{A|B}$, and the right boundary will be the right side of $\mathbf{RVO} _{A|B}$.

For the left rule, the procedure is nearly the same as described above, just exchanging right and left. The $\mathbf{RVO} _{A|B}$ at that time will be expanded to the right to encourage robot A to take the left side of robot B to pass. Figure 2(b) will illustrate the steps to construct the SHRVO for left rule.

The apex of L-SHRVO is the intersection between the left side of $\mathbf{RVO} _{A|B}$ and the right side of $\mathbf{VO} ^\prime _{A|B}$. Two boundaries of SHRVO for left rule will be the right side of $\mathbf{VO} ^\prime _{A|B}$, and the left side of $\mathbf{RVO} _{A|B}$.

$$\begin{aligned} \mathbf{apex} = \text{ left } \mathbf{RVO} _{A|B} \cap \text{ right } \mathbf{VO} ^\prime _{A|B} \end{aligned}$$

(6)

3 Experiments

The effectiveness of the proposed social HRVO model is verified by implementing and testing in a simulation environment. The C/C++ programming language is applied to implement the proposed system, while the Robot Operating System (ROS) [11] is utilized to develop the entire navigation framework. The original HRVO package¹ was inherited and adjusted to develop the proposed social HRVO model.

3.1 Simulation Setup

We create scenarios, as shown in Figs. 3, 4, 5 and 6, in which the mobile robot need to cooperate with the behaviors of other humans in the environments to reach its goal. In addition to guarantee the collision-free, the robot is required to follow the social rules such as passing on the right side or left side of other humans. With the aim of demonstrating the performance of the proposed social HRVO model, we compare it with the original hybrid reciprocal velocity obstacle model HRVO [15]. Furthermore, the proposed socially aware navigation framework is validated by adopting the human comfortable safety indices (HCSI) introduced by Truong et al. [19], including social individual index (SII), social group index (SGI). The HCSI indices are used to estimate the human safety and comfort and socially acceptable behaviors of the mobile robot. Specifically, the SII value is applied to measure the physical safety and psychological safety of each individual, while the SGI is used to measure the comfortable safety of the human group.

3.2 Simulation Results

Videos with our simulation results can be found at the links²$^,$³$^,$⁴ and⁵.

Fig. 3.

The simulation results of cooperative avoidance of a robot when avoiding a person. The first and third rows, from left to right, show the trajectory of the robot and the human equipped with the R-SHRVO model, L-SHRVO model and the conventional HRVO model, respectively. The second and fourth rows illustrate the corresponding social individual index (SII).

Experiment 1 – Avoiding a Person: We first examine the proposed SHRVO model in a simulation environment with a person. The mobile robot is expected to move from left to right without any collision with a moving person. The simulation results are shown in Fig. 3. The first and third rows show the trajectory of the robot and the person, and the second and fourth rows illustrate the SII value along the robot’s trajectory.

In Figs. 3(a) and 3(b), the mobile robot equipped with the proposed SHRVO technique successfully cooperates with the moving person to avoid each other on the side that we preconfigure in the algorithm. In contrast, the robot and the person select the left side to avoid if it is installed the conventional HRVO model in Fig. 3(c). Similarly, in Figs. 3(g) and 3(h), the robot successfully overtakes on the side following the rule which is installed in the SHRVO model, whereas left side is the selection of the robot and the person with the HRVO model as shown in Fig. 3(i).

Figures 3(d), 3(e), 3(f), 3(j), 3(k) and 3(l) show that, when equipped with the SHRVO model, the mobile robot not only successfully cooperates with the moving person to overtake or avoid but also still maintains a safety distance with the person.

Fig. 4.

The simulation results of cooperative avoidance of the robot and a group of two people in opposite directions. The first row, from left to right, shows the trajectory of the robot and the humans equipped with the R-HRVO model, L-HRVO model and the conventional HRVO model, respectively. The second and third rows illustrate the corresponding social individual index and social group index (SGI).

Experiment 2 – Avoiding a Group of Two People: In this experiment, we want to verify the avoiding behavior of the mobile robot when avoiding a group of two people moving towards the robot. The simulation results are shown in Fig. 4, in which the first row shows the trajectory of the robot when passing two people, while the second and last rows illustrate the SII and SGI values along the robot’s trajectory, respectively. In the first row of Fig. 4, by cooperating with the behaviors of two people, the mobile robot equipped with the proposed SHRVO algorithm, as presented in Figs. 4(a) and 4(b), or the HRVO algorithm, as presented in Fig. 4(c), is able to safely navigate to its goal.

Although the SII values in Fig. 4(d), Fig. 4(e) and Fig. 4(f) are similarly low indicating that the robot equipped with both SHRVO and HRVO models often maintains a safety distance with each person, the trajectory of HRVO model goes through the interaction space between two people. This is the reason for the much higher SGI value of HRVO model in Fig. 4(i) in comparison with the SGI values in Fig. 4(g) and Fig. 4(h) of SHRVO model. Therefore, in this experiment, the robot installed the SHRVO model offers a higher safety distance with the group of two people than the HRVO model.

Fig. 5.

The simulation results of cooperative avoidance of the robot equipped with R-SHRVO model when avoiding dynamic people. The first row shows the trajectory of the robot and two humans in different situations, while the second row, from left to right, illustrates the trajectory of the robot and three people, four people and a crowd of people, respectively.

Fig. 6.

The simulation results of cooperative avoidance of the robot equipped with L-SHRVO model when avoiding dynamic people. The first row shows the trajectory of the robot and two humans in different situations. Whereas, the second row, from left to right, illustrates the trajectory of the robot and three people, four people and a crowd of people, respectively.

Experiment 3 – Avoiding Dynamic People: The successful performance of the proposed SHRVO model is further clarified in several crowded environment scenarios, in which many people are moving toward the robot or in the same direction. The simulation results are shown in Fig. 5 and Fig. 6.

In Fig. 5, the simulation results show that the mobile robot equipped with the R-SHRVO algorithm successfully cooperates with the humans to guarantee the collision-free by selecting the right side to avoid each other. Especially, when one of two people is to the right of the robot as shown in Fig. 5(c) or there are a crowd of people in the environment as shown in Fig. 5(f), the robot still chooses the right side to avoid the humans if it is installed the R-SHRVO model.

Similarly, Fig. 6 illustrates that the robot equipped with the L-SHRVO model also succeeds in navigating to its goal without any collision by selecting the left side to avoid the humans. The successful performance of the L-SHRVO model is demonstrated even if one of two people is to the left of the robot as shown in Fig. 6(b) or there are a crowd of people as shown Fig. 6(f).

In summary, the simulation results illustrate that, the robot equipped with the proposed SHRVO model is capable of cooperating with the humans in the crowded environment, and safely and socially navigating to the given target.

4 Conclusion

We have presented a social hybrid reciprocal velocity obstacle (SHRVO)-based navigation framework which ensures the free collision and social behavior for a mobile robot while navigating in dynamic social environments. In our proposed system, the social rules are integrated into the conventional HRVO algorithm to construct the SHRVO model. We have executed many simulation experiments to verify the proposed framework and the results demonstrate that our developed system can be able to navigate the mobile robot safely and humanly in dynamic social environments.

In the future, we will install the proposed SHRVO model on our mobile robot platform, and conduct experiments in real-world environments.