{'fraction_non_alphanumeric': 0.024692720983292855, 'fraction_numerical': 0.008979171266651946, 'mean_word_length': 4.7030430220356765, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Autonomous Mobile Robot Navigation in Uneven and Unstructured Indoor Environments

Robots are increasingly operating in indoor environments designed for and shared with people. However, robots working safely and autonomously in uneven and unstructured environments still face great challenges. Many modern indoor environments are designed with wheelchair accessibility in mind. This presents an opportunity for wheeled robots to navigate through sloped areas while avoiding staircases. In this paper, we present an integrated software and hardware system for autonomous mobile robot navigation in uneven and unstructured indoor environments. This modular and reusable software framework incorporates capabilities of perception and navigation. Our robot first builds a 3D OctoMap representation for the uneven environment with the 3D mapping using wheel odometry, 2D laser and RGB-D data. Then we project multilayer 2D occupancy maps from OctoMap to generate the the traversable map based on layer differences. The safe traversable map serves as the input for efficient autonomous navigation. Furthermore, we employ a variable step size Rapidly Exploring Random Trees that could adjust the step size automatically, eliminating tuning step sizes according to environments. We conduct extensive experiments in simulation and real-world, demonstrating the efficacy and efficiency of our system.


I. INTRODUCTION
Autonomous mobile robot navigation plays a vital role in self-driving cars, warehouse robots, personal assistant robots and smart wheelchairs, especially with a shortage of workforce and an ever-increasing aging population. Significant progress has been achieved in recent decades advancing the state-of-the-art of mobile robot technologies. These robots are operating more and more in unknown and unstructured environments, which requires a high degree of flexibility, perception, motion and control. Companies such as Google and Uber are developing advanced self-driving cars and expecting to present them into the market in the next few years. Various mobile robots are roaming in factories and warehouses to automate the production lines and inventory, saving workers from walking daily marathons [1]. Robot vacuums such as Roomba and Dyson360 eyes are moving around in the house to help clean the floors. Personal robots Fig. 1: The robot is navigating up the slope to the goal at the higher platform. In the presence of staircases and slope, our robot first builds a 3D representation of the environment to generate the traversable map, and then the robot can navigate through the slope and avoid the staircases to reach the goal efficiently and safely. such as PR2 [2], [3] and Care-O-bot [4] have demonstrated the ability to perform a variety of integrated tasks such as long-distance navigation and complex manipulation.
Mobile robots navigating autonomously and safely in uneven and unstructured environments still face great challenges. Fortunately, more and more environments are designed and built for wheelchairs, providing sloped areas for wheeled robots to navigate through. However, little work focuses on an integrated system of autonomous navigation in sloped and unstructured indoor areas, especially narrow sloped areas and cluttered space in many modern buildings. The robots are required to safely navigate in narrow uneven areas such as those shown in Fig. 1 while avoiding static and dynamic obstacles such as people and pets.
In this work, we present an integrated software and hardware framework for autonomous mobile robot navigation in uneven and unstructured indoor environments that are designed for and shared with people. Fig. 2 shows a highlevel system architecture of this work. Our robot first builds a 3D OctoMap representation for uneven environment with our 3D simultaneous localization and mapping (SLAM) using wheel odometry, a 2D laser and an RGB-D data. Then multi-layer maps are projected from OctoMap to generate the traversable map which serves as the input for our path planning and navigation. The robot employs a variable step size RRT approach for global planning, adaptive Monte Fig. 2: High-level system architecture. The robot first builds a 3D OctoMap representation for uneven environment with the present 3D SLAM using wheel odometry, a 2D laser and an RGB-D data. Multi-layer maps from OctoMap are used for generating the traversable map, which serves as the input for autonomous navigation. The robot employs a variable step size RRT approach for global planning, adaptive Monte Carlo localization method to localize itself, and elastic bands method as the local planner to gap the global planning and real-time sensor-based robot control.
Carlo localization method to localize itself, and elastic bands method as the local planner to close the gap between global path planning and real-time sensor-based robot control. Our focus is especially on efficient and robust environment representation and path planning. It is believed that reliable autonomous navigation in uneven and unstructured environments is not only useful for mobile robots but also could provide helpful insight on smart wheelchair design in the future.

II. RELATED WORK
Building autonomous robots that assist people in human environments has been a long-standing goal [5] and an appealing inspiration of research in robotics. Robots have demonstrated various levels of success but still face challenges.
RHINO [5] integrates a distributed autonomous navigation architecture dedicated to human robot interaction with various sensors. Minerva [6] focuses on the probabilistic paradigm of environment, robot , sensors and models, setting the foundation for the probabilistic robotics epoch. Besides autonomous navigation, Robox [7] integrated multi-modal interaction, speech recognition, and multi-robot coordination. Curious George [8] could use visual attention locate the objects of interest in an environment. Jinny [9] can select the proper motion strategy according to different environments. Sonar or laser range finders are usually positioned on these robot to build 2D maps along a horizontal slice of the world [10]. However, just one slice of the space can not represent the environment, especially uneven environments with slopes and staircases.
Three-dimensional (3D) environment sensing such as 3D Lidar which is on self-driving cars [11], 2D laser-rangefinder with a pan-tilt unit [12], [13], or affordable RGB-D sensors is increasingly common. A 3D SLAM algorithm using 3D laser range finder is presented in [14] which represents the world with point clouds, but neither free space nor unknown areas are modeled. Vision based 3D SLAM [15], [16], [17], [18] with affordable RGB-D sensors are increasingly popular since the introduction of KinectFusion [19]. These methods usually rely on iterative closest point registration (ICP) [20] or local features matching based method or the integration of both. However, the ICP method is only confined to desk area [19], while the local feature based methods are not robust in environments where white walls and dull floors dominate with few local features. Moreover, these methods only focuses on environment representation, without integrating autonomous navigation as an integrated system and demonstrating their overall performance. Autonomous navigation with a compact 3D representation of the environment is represented in [2], but only a layer of projected 2D environment representation is used for navigation. A combination of multi-layered 2D and 3D representations are used in [3] to improve planning speed, but only for an even environment. Robot autonomous navigation in full 3D environment is presented in [21], but it is designed for legged robots navigating through staircases. Moreover, the real-time interpreting and updating of 3D data still poses great challenges for low power laptops. These slow updates result in the robot either moving slowly or in a potentially unsafe manner.
Some work focuses on uneven outdoor terrain. A rulebased fuzzy traversability index has been used [22] to quantify the ease-of-traversal of a terrain by a mobile robot based on measurements from image data. Online kernelbased learning is proposed to estimate a continuous surface over the area of interest while providing upper and lower bounds on that surface with 3D laser [23]. However, these uneven outdoor terrains are very different from indoor uneven environments. Indoor environments tend to be mostly even, and often contain slopes for wheelchair accessibility. With robots or smart wheelchairs are operating in shared spaces indoors with people more and more, challenges operating in uneven and unstructured environments, especially in those designed for wheelchair mobility shall be addressed in the robotics community.

III. THE ROBOT HARDWARE AND SOFTWARE PLATFORM
The development of a mobile robot system to work around us and assist people is our long-term goal. The main design principle for the developed system is that each hardware and software component could work as both a single module and a part of an integrated system. To realize this principle, these hardware components are assembled using screws and adjustable frames, while the software platform uses the Robot Operating System (ROS) [24]. Fig. 3 shows the hardware platform for our robot. It includes a Segway RMP100 mobile base, an ASUS Xtion on the upper base, a Hokuyo UTM-30LX laser scanner mounted on the lower base, and a DELL laptop with Intel Core i7-4510U at 2GHz, 16GB memory (without GPU).
The software system is implemented in ROS Indigo release on top of an Ubuntu version 14.04LTS operating system. The 3D simulation experiments are performed on Gazebo [25]. Fig. 2 illustrates a high-level software architecture, and detailed key components of the software architecture will be described in Sec IV and V.

IV. ENVIRONMENT REPRESENTATION
A consistent and accurate representation of the environment is a crucial component of autonomous systems as it serves as input for motion planning to generate collisionfree and optimal motions for the robot.
A. 3D mapping using wheel odometry, a 2D Laser and an RGB-D camera 3D mapping pipelines commonly consist of localization and mapping components. Localization is the process to estimate robot pose, and mapping (or fusion) involves integrating new sensor observations into the 3D reconstruction of the environment. To overcome the challenge that vision based SLAM is not robust when the environment lacks local features, we employ wheel odometry, a 2D laser and an RGB-D camera concurrently to complement each other. Our 3D Mapping framework builds on top of Karto SLAM [26], a 2D robust SLAM method containing scan matching, loop detection, Sparse Pose Adjustment [27] as the solver for pose optimization and 2D occupancy grid construction. Karto SLAM takes in data from the laser range finder and wheel odometry. It is the best performing ROS-enabled SLAM technique in the real world, being less affected by noise [28] compared with other 2D SLAM methods, such as gmapping [29], HectorSLAM [30] and GraphSLAM [10].
Instead of using Karto SLAM's default 2D occupancy map, which we found cannot represent uneven environment reliably, we build the environment based on OctoMap [31]. It is a probabilistic, flexible, and compact 3D mapping method which can represent the free, occupied and unknown environment. At each time step, the algorithm accepts point clouds of the environment using the RGB-D sensor and the localization information from the Karto SLAM using a 2D laser and wheel odometry. Fig. 4(b) shows an OctoMap representation of the simulated world generated by our 3D mapping. Note that free space is explicitly modeled in the experiment but is not shown in the figure for clarity.

B. Multilayer maps and traversable map
After the environment is represented by OctoMap as mentioned above, the OctoMap is cut from bottom to top with several layers depending on the environment and the required accuracy. Then these multilayers are integrated into a traversable map, which is safe and efficient for the robot to navigate through. Both the multi-layer maps and the traversable map are represented as 2D grid occupancy maps, in which black represents occupied space, white as free space, and gray as unknown space. A flag F is used to mark the map traversablility and decide whether an area is traversable: where θ represents the angle threshold which can be set according to the robot climbing capability. α i is the ith layer where d represents the distance between projected layers, as shown in Fig. 5 (a). It can be set to be as small as the resolution of the OctoMap for accurate representation. l j i represents the length of the edge difference between different layers, and it can be obtained through the number of voxels v j i in that area and OctoMap resolution r. Take the environment in Fig. 4 (a) as an example, first we project four layers of 2D map from the OctoMap as shown in Fig.  5 (a) and the left four maps in Fig. 5 (b). Then the gradient between layers are checked, for instance, in Fig. 5 (a), both α 1 and α 2 are less than θ, and that area is marked as a slope while β 1 and β 2 are larger than θ, that area is marked as an untraversable area. At the same time, the left and right edges of the slope are marked as occupied for safety. Integrating all these multi-layer maps will generate the traversable map as shown in Fig. 5 (b), which is very efficient for the mobile robot to use.

V. PLANNING AND NAVIGATION
The traversable map serves as the input for the planning and navigation framework. We apply an efficient variable step size RRT planner as our global planner to construct a plan in a configuration space C to reach the goal.
The global planner generates a list of way-points for the overall optimal path from the starting position to the goal Algorithm 1: Variable Step Size RRT Input: Start point q s , Goal point q g , C f ree , C obst Output: Path from q s to q g with several nodes 1 Initialization; 2 Establish a direct connection l init between q s and q g ; 3 if CollisionCheck(l init ) then 4 Return path l init ; 5 else 6 Get two points from l init as new start and end point ; if CollisionCheck(P temp ) then 14 x i rand ← the point near obstacle ;

A. Global planner: variable step size RRT
It is crucial that the global planning process should be efficient so that the navigation system can run at a reasonable rate. Rapidly Exploring Random Trees (RRT) [32] can handle problems with complex constraint and obstacles and perform well in high dimensional environments. It is good for our current setup and is also promising for integrating full 3D planning in the future. However, it needs to adjust the step size according to the environment, which is an inconvenient trial-and-error process. Therefore, we introduce a variable step size RRT for our global planning. In the tree extending process of standard RRT, we get a sampling point x rand and then find the nearest point x near in the existing tree. If the segment that connects points x rand and x near is collision free, we move from point x near to x rand with limited step size σ, getting a new point x new that would be added to the existing tree. In [33], the extension process of RRT could be different for holonomic and nonholonomic systems. The latter can use the standard tree extending process while for the former, x new could be x rand in order to facilitate exploration. For a nonholonomic system, like the Segway robot we used in our experiment, it is important to choose the right σ. The RRT algorithm runs slowly when σ is set small, i.e, with a small step size, it is slow to find the target. However, if σ is too big, then the path generated by RRT will jitter, which is too long and inadequate for further trajectory optimization. Thus with standard extending process of RRT, it is vital to choose the proper σ according to different environments.
According to our navigation framework that employs both global planner and local planner, the global path planner could be sub-optimal since the local planner would optimize the global path incrementally. Hence we propose to use a variable step size RRT that is originally used for holonomic systems. Our algorithm is illustrated in Algorithm 1. The main difference lies in the tree extending process. When a point x nearest is generated, instead of moving from the point to x rand with a limited step size, we connect the two points directly, and we get a line l. If l passeses the collision checking process, then it is added to the tree directly. While if l collides, the last point along the line would be x new and the point together with the line between x new and x nearest would be added to the tree. We recommend readers to read the our previous work [34] for more details. In addition, in order to deal with targets that lie in a narrow region, in which it will take longer before enough sampling points are chosen, we employ the idea of the RRT-connect algorithm [35], extending the tree from both the start and the goal position. The advantage of our method is that there is no need to adjust the parameter σ in different environments. Whilst we try to extend the tree with the biggest step size, the planner can cover the configuration space with relatively small sampling points. Hence saving the time of collision checking of sampling points and finding the nearest point in the existing tree.   Please refer to Sec VI for more details of these representative tasks. Fig. 6 demonstrates the comparison between RRT of different step sizes and our proposed variable step size RRT. Fig. 6 (a) shows that when the step size is small, it takes 171 iterations to reach the goal. When the step size is large such as 90 as shown in Fig. 6 (c), it oscillates and takes 166 iterations to reach the goal. While our variable step size only takes 73 iterations to reach the goal. The standard RRT may outperform our method if the step size is adjusted properly, as shown in Fig.6. However, in real implementation, our method does not need to adjust the step size in different environments and can achieve better comprehensive performance.

B. Localization and local planner
Mobile robot localization is the problem of determining the pose of a robot relative to a known environment [10]. The robot employs adaptive Monte Carlo localization (AMCL) [36], a method that uses a particle filter to track the pose of the robot with a known map. It takes laser scans, the wheel odometry information and the traversable map, and then outputs pose estimation.
The local planner is seeded with the plan produced by the global planner, and attempts to follow it as closely as possible while taking into account the kinematics and dynamics of the robot as well as the obstacle information. We use Elastic Bands method [37] as our local planner to close the gap between global path planning and real-time sensor-based robot control.
During execution, the short and smooth path from the local planner is converted into motion commands for the robot mobile base. The local planner computes the velocities required to reach the next pose along the path and checks for collisions in the updated local costmap.

VI. EXPERIMENTS
Extensive experiments are conducted to evaluate the developed system both in simulation and real-world, demonstrating the efficacy for real-time mobile robot autonomous navigation in uneven and unstructured environments. It is notable that our focus is also on an integrated system besides the component methods.

A. Simulation experiments
The simulation is conducted in Caffe using an environment of size 13m x 10m x 3m, which we built in Gazebo. A Fig. 7: Autonomous navigation in the simulated environment. The first row shows images of autonomous navigation in Gazebo, and the second row shows the Rviz views of the process. For the whole process, please refer to our attached video. visualization is shown in Fig. 4. The simulated robot model is equipped with wheel odometry, a 2D laser range finder and an RGB-D sensor. At the stage of 3D Mapping, the robot subscribes the point clouds from the RGB-D camera and the localization information from the 2D SLAM. Then the point clouds and localization information is fed to the Octomap server. The robot is tele-operated to move around the environment. Fig. 4 (b) shows the OctoMap generated by our 3D Mapping. The resolution of the OctoMap is set as 0.05m to trade off between speed and accuracy, and the threshold on the occupancy probability is 0.7. Note that free space is explicitly modeled in the experiment but is not shown in the figure for clarity.
The Octomap is then sliced and projected to four intersection planes as shown in the left part of Fig. 5 (b). More planes could also be chosen depending on the accuracy necessity and the complexity of the environment. It can be seen that the staircase area shows steeper changes than the sloped area. Therefore, in the generation of the traversable map, we treat the steeper changes as untraversable area while the area with slower changes as the slope. The right part of Fig. 5 (b) shows the generated traversable map, which will be used for our robot autonomous navigation.
For autonomous navigation, we use the traversable map and sensors data as the input for path planning and localization. We conducted various autonomous navigation experiments in which the robot starts and reaches goals at different positions. Task-1 and Task-2 in Table I show some statistics of reaching the target on the ground and on higher platform respectively. Our variable step size path planner is very efficient, and only takes several milliseconds to reach the goal position. Under the speed constraint of 1m/s, the robot can reach the target relatively fast. Fig. 7 illustrates an example of our robot autonomous navigation process in Task-2 in which the robot starts at lower ground and reaches the goal in the higher platform. The blue and green lines show the exploration process of our global planner. This process ended after a global path connecting the start point and the end point is found, shown in the red line. The local path planner can smooth the global path if it is not optimal, and the optimal path is marked as a concatenation of green bubbles. Fig.7 (b) -Fig.7 (c) show the replanning process when an obstacle is found. If the height of a slope is higher than the laser on the robot, then the robot would consider there is an obstacle ahead. The robot can replan its path when this occurs. Fig.7 (d) - Fig.7 (e) show the replanning process of local planner when a real obstacle appears. The robot can avoid the obstacle and reach the target position.

B. Real-world experiments
We conduct extensive experiments with our Segway Robot in the real-world environment. Fig. 8 shows our real environment with dimension of 11mx5mx3m, and the 3D OctoMap generated from our 3D mapping with wheel odometry, 2D laser and RGB-D data. At this 3D mapping stage, we teleoperate our Segway robot to move around the environment. Compared with the simulated environment, the real environment features challenges such as narrower slopes, different lighting conditions, and glass windows. The real robot is much more noisy due to long-term wear-and-tear, uncalibrated wheel odometry, and the disturbance of casters. The sensors are also noisier. Therefore, the OctoMap of the real environment and projected multi-layer maps in Fig. 9 tend to have some distortions and inconsistent registrations compared with the simulated environment. All these noisy environment, robot and sensors demand robustness of our system. The resolution of the OctoMap is experimentally set to 0.05m to trade off speed and accuracy. We also use four layers of projected maps to generate the traversable map in the real environment. The traversable map in Fig. 9 (e) will serve as the input for path planning and localization in autonomous navigation. We present several representative tasks for the robot in our experiment in which all goal positions are located at higher platforms. In Task-3, the robot needs to navigate through the slope to reach the target from a far away starting position at ground level. In Task-4, shown in Fig. 10, the robot starts near the slope but faces the staircase. With the traversable map, the robot could plan a path to avoid the staircase and navigate through the slope to reach the goal position. Since the route contains many turns, the robot moves more slowly in this task. In Task-5, we test the dynamic obstacle avoidance ability of our system. A human suddenly appears and blocks the path of the robot, forcing the robot to replan and change directions to avoid the human. The average plan and replan time when encountering the obstacle is about 10ms. The robot can successfully avoid the obstacle and replan its path to the goal. In this dynamic obstacle case, the robot moves with a relatively low speed so as to safely avoid the obstacle. Fig. 11 illustrates some of the procedures. Table  I demonstrates the overall statistics of these representative tasks.
One important parameter for robot navigating up the slope is the size of local costmap [38]. If the local costmap size is set too large, the far away ray sweep of the laser scan on the slope will intersect with the higher part of the slope, causing obstacle in the local costmap, which will block the robot's path. It is especially obvious in the more noisy real experiment in which the robot is prone to fail in localizing itself than in simulated environment. In case of localization failure, the robot will initiate the rotation recovery mode, in which the robot rotates and laser-sweeps in a circle. If the local costmap size is too small, the obstacles may not be considered in time, which may cause unsafe collision. We experimentally determined the costmap of 3 meters width and 4 meters length to work best for the use in this case.

VII. CONCLUSION AND FUTURE WORK
In this paper, we presented an integrated software and hardware architecture for autonomous mobile robot navigation in 3D uneven and unstructured indoor environments. This modular and reusable software framework incorporates capabilities of perception and navigation. We employ an efficient path planner which uses variable step size RRT in 3D environment with an octree-based representation. We generate a safe and feasible 2D map from multi-layer maps of 3D OctoMap for efficient planning and navigation. We demonstrate and evaluate our integrated system in both simulation and real-world experiments. Both simulation and realrobot experiments demonstrate the efficacy and efficiency of our methods, providing some insight for more autonomous mobile robots and wheelchairs working around us. Future work may integrate vision-based global localization [39] [40] and optimized path planning methods into our system. Moreover, it is promising to explore the possibility of using 3D semantic scene parsing [41] to understand the uneven areas and better differentiate between slopes and staircases.