IROS2019国际学术会议论文集 0723

Abstract Auto exploration is a task for self driving robots to explore unknown environments which becomes much complicated when they move on irregular outdoor terrains To improve the situation a new frontier based exploration algorithm is presented in this paper It starts from original 3D cloud points of the environment to analyze the traversability of the scanned area and further provides a reachability map to mark all map grid cells as reachable dangerous or unknown Frontier candidates are obtained from the reachable map then clustered and reduced using an improved K means Finally the target of next exploration step is selected from the frontiers left by evaluating their travel cost The algorithm is validated on an irregular outdoor terrain and shows the capability for a field robot to explore on an irregular terrain I INTRODUCTION When a robot is made to work in unknown environment without any human intervention the capability of autonomous exploration is crucial in achieving tasks such as environment modeling target searching and auto navigation 1 A common requirement of an autonomous exploration mission is to determine the target location of the next step of movement A series of such continuous movements would complete the exploration of the unknown surrounding space and provide necessary information for the ultimate tasks such as rescue inspection and surveillance 2 A typical exploration process is described as follows 3 4 5 firstly a laser scanner or other detection sensors mounted on the robot take views of its surrounding environments and transform the sensor data to a local map in the robot coordinate frame secondly the global map of the environment is updated by merging the newly acquired local map with the current localization of the robot deduced with dead reckoning techniques finally the next best observation position named as sub target in this paper is determined according to some exploration strategy and the robot would navigate there autonomously The robot performs the above process iteratively until a certain mission is completed In this paper we will focus on the third step to provide a desirable and achievable sub target position for the robot to explore in irregular and complex unknown environments Maximizing the view coverage is the main purpose of the exploration actions In previous studies one common way to determine the sub target is to find the frontiers in the map which are defined as boundaries between known and unknown spaces 6 7 8 9 The frontiers are treated as the candidates of The authors are with the School of Mechatronics Engineering and Automation Shanghai University Shanghai Key Laboratory of Intelligent Manufacturing and Robotics No 99 Shangda Rd Shanghai 200444 PR China Institute of Aerospace System Engineering Shanghai No 3805 Jindu Rd Shanghai 201109 PR China Y X phone 86e mail xieym the sub target so that the unknown terrain can be viewed at the next stop Usually the closest frontier is chosen as the sub target to save the driving cost 10 11 12 Since choosing only by distance is lack of consideration on the differences of expected information gains among various frontiers the selection criterion is further developed to balance the requirements from short travelling distance and more information gains Andreas Bircher and Mina Kamel 13 proposed a strategy to seek out the node with highest collected information gain which is the summation of the unmapped volume that can be explored on the way to the next observation position Wenchao Gao 14 designed a new utility function for optimal frontier assignment by considering the robot travelling distance the frontier size and the turning cost simultaneously Due to the abundance of frontier cells obtained in a 3D environment they are segmented in order to improve the computational efficiency In the prior work of 15 a histogram based approach was adopted to cluster frontier cells and score these clusters based on their distances from the current robot location and the number of frontier cells in them Senarathne et al 16 developed an efficient approach to segment frontiers by only detecting intermediate changes to cells in the current exploration map and only the updated cells were considered for the frontier segmentation Belavadi et al 17 employed K means clustering technique to divide the frontier cells into partitions The centroids of the frontier clusters were set as sub target candidates to be evaluated by the cost function How to select the best sub target from the frontier candidates is well studied as stated above while how to determine whether a location is a frontier is still based on much simplified assumptions in previous studies Usually the terrain cells are marked as free unknown and occupied The status of a cell can be used to find the frontiers in exploration by checking its neighbors 18 19 Such method might be valid for 2D regular indoor environments but not feasible for mobile robots driving on irregular terrains When the surrounding terrain is rough it is hard to simply mark a cell as free or occupied Instead the grid cell should be categorized as traversable danger or unknown for a certain robot Since the original environmental information is usually measured as a cloud point map it is critical to analysis the traversabiltiy of the cells from its original measurement data by examining the kinematic interaction relationship between the terrain and the robot Aiming to solve this problem in this paper we provide an autonomous exploration algorithm for irregular terrain conditions which focuses on finding the sub target with traversability analysis using the original cloud point measurement data An autonomous exploration algorithm using environment robot interacted traversability analysis Yujie Tang Jun Cai Meng Chen Xuejiao Yan Yangmin Xie 2019 IEEE RSJ International Conference on Intelligent Robots and Systems IROS Macau China November 4 8 2019 978 1 7281 4003 2 19 31 00 2019 IEEE4885 The rest of the paper is organized as follows In part II an extended traversability map is introduced and obtained from the original measurement data Part III describes the criterion of determining the frontiers and the algorithm to choose the sub target Part IV provides experimental validation of the algorithm and Part V concludes the paper II EXTENDED TRAVERSABILITY MAP Figure 1 The structure of the traversability maps in this paper A traversability map indicates the difficulty that a robot would encounter when traversing through an area Generally a traversability index is assigned to each grid cell of a map 19 or an irregular triangulate map 20 to represent the local driving safeness In most cases the index is calculated purely based on the terrain geometry 21 without particularly considering the robot kinematics In this section we will show a traversability assessment using the 3D cloud point map In such a way the driving safety is not only determined by the terrain condition but also the interactive relationship between the robot and the ground surface when it is placed at a specific position and direction It would improve the reliability of the traversability assessment especially in challenging outdoor environments A Traversability map definition In this paper both position and placement direction of the robot are considered in calculating the traversability index The space is discretized by the size of approximately half of the wheel radius and it can be adjusted by scenarios The traversability map then has the structure shown in Fig 1 named extended traversability map in this paper Each cell in the map is accessed by eight directions i j adenotes the cell with i and j as the indexes in the x and y directions and 1 1i jij F denotes the traversability weights when the center of the left front wheel is placed at the center of i j a in the direction from i j ato 1 1ij a Therefore there are totally 8 traversability weights corresponding to the 8 placement directions of the robot when it locates at i j a The corresponding angles between the robot s proceeding direction and the x axis in the terrain coordinate system are 0 45 90 135 180 45 90 and 135 degrees A cell is defined as unknown when there is none cloud point within it To get 1 1i jij F from the cloud point data a traversability analysis is illustrated in the following subsections B Traversable and Danger cells Being tipped over or slipping at steep slopes are two main hazards that need to be addressed when driving through unknown territories Most of the previous research use only the estimation of the terrain slope and roughness to evaluate the possibility for the two hazards to happen which is not sufficient when the terrain shape is much complicated In the limited number of literatures incorporating robot properties only static cases are considered generally 22 23 Accurate dynamic model is hard to obtain because it not only involves the robot dynamics which is already complex for certain systems but also highly related to the complicated wheel terrain interaction mechanism Therefore we adopt static analysis in this paper which means only the situations that the robot sits statically on the terrain are examined The robot is simplified as shown in Fig 2 with the critical geometric parameters as the distance between left and right wheels W the distance between front and rear wheels L the radius of the wheel R and the height of the chassis H The robot coordinate system is defined to have the origin at the center of the left front wheel For the particular robot considered in this paper R 12cm L 35cm W 47cm H 9cm L W R AB CD H The ground XC YC ZC OC Figure 2 A simplified geometric model of the robot To calculate the projection of the robot on x y plane in Fig 3 the centers of the four wheels on the terrain map in the x y plane is obtained using the formula in Eq 1 where C is the coordinate of a specific point in the robot coordinate system M is the corresponding coordinate in the terrain map coordinate system is the angel of the placement direction and xy T T T is the translation vector from the current robot coordinate system to the terrain map coordinate system cossin sincos MC T 1 Correspondingly the footprints of the four wheels on the terrain map are defined as four circles with radius of R centered at A M B M C M D M respectively Fig 3 Technically the four wheels cannot be guaranteed to be all on 4886 the ground simultaneously when the robot is driving on uneven terrains Without a strict dynamical analysis which is not realistic under the current circumstance it is impossible to determine which three wheels would be on ground at the current location Therefore we choose to consider all the four possibilities That is as shown in Fig 3 to examine all the four cases when wheels ABC ABD ACD BCD are on the ground respectively For each case the terrain cloud points of the corresponding footprints are fit as a plane The vector 1 2 3 4 w w n represents the normal vector of the plane for each case and the angle w between w n and the vertical vector W Zis the estimation of the inclination of the robot chassis Fig 4 The corresponding planes are obtained by PCA Principal Component Analysis technique and the normal vector of the fitted plane is the eigenvector corresponding to the minimal eigenvalue of the resulted covariance matrix w Cwhich is defined in Eq 2 The corresponding plane equations can be obtained by Eq 3 and the angle is calculated using Eq 4 As the force angle relationship stated in many literatures 24 the larger the angle w is the more dangerous the robot is at the current location and driving direction Figure 3 Footprints of the robot and the four corresponding fitted planes to estimate the robot pose Figure 4 The tilt angle of the robot 1 w k T w i w 1 k iwwiww Cq q q q 2 0 x y z www nnq 3 2 arcos w w n wW nZ 4 where iw q is the cloud point set whose projection on the x y plane belongs to one of the footprint cases ABC ABD ACD and BCD w kis the number of the points in the set and w q is the average value of the point set Plane AB CD Figure 5 Chassis collides with obstacle points Another incident that could cause damages to the robot is when the chassis collides with the obstacles on the ground This could happen even when the four wheels sit safely on relatively flat ground without danger of tip over or slipping as shown in Fig 5 The danger of chassis collision can be checked by calculating the relative relationship between the chassis plane and the terrain surface points The chassis is assumed to be parallel with the footprint planes For each of the footprint case ABC ABD ACD BCD the chassis plane is obtained by making a plane shift 0 x yH z www nnq 5 Denote the terrain cloud points within the square ABCD M M M M as MS P and for each point MS pP it collides with the chassis when H www npnq 6 The extended traversability map in Fig 1 will be finally obtained in Eq 7 For the cells where none cloud point exists they are marked as unknown Mark as unknown cell F occlusion chasis colli there is none clo son max Mark as unpassable in the dir ud point within the cell ection F i j m n w i j m n if else if Mark as passable in the direction F0 i j m n else end end 7 where is the largest allowed tilt angle m n m i 1 i i 1 n j 1 j j 1 represents the placement direction of the robot and are constants which suggested be as large as possible 4887 III FIND THE SUB TARGET A Define the frontiers The traversability map discussed in Section 2 provides the assessment on whether the robot can pass through a cell in different directions considering the interaction between the terrain and the robot In previous studies a volumetric map such as Octomap 25 is usually used to represent the occupancy of the environment by marking the cells as free occupied and unknown areas A reachability map which serves similar purpose as the occupancy map in previous research and reduces the dimension of the traversability map should be further obtained on the purpose of finding proper frontiers In which the unknown cells remain to be unknown However only the cells which are passable in all directions marked as reachable In detail the reachability map is defined in Eq 8 for arbitrary point i j a F 1 1 1 1 Mark as unknown cell F 1 1 1 1 Mark as dangerous cell i j m n i j i j m n i j ifmii injj j a else ifmii injj j a else Mark as reachable cell i j a end end 8 The planer reachable map encodes the cells as unknown reachable and dangerous In the commonly used frontier based methods a frontier is defined as a boundary that separates known regions from unknown ones In this paper frontier candidates are defined as the positions at the boundaries between reachable areas and unknown areas The frontier candidates are found as the reachable cells that at least one of their neighbors are unknown The frontier candidates in the map may be numerous scatter and irregularly distributed A clustering technique is further developed to partition the frontier candidates and leaves limited number of frontiers A k means clustering method is implemented here to cluster the frontier candidates into k clusters so that only the cluster centers need to be considered The details of the K mean method are referred to the work of Belavadi in 17 One drawback of this technique is the necessity of having prior knowledge of the frontier s layout to decide the optimal number of the clusters to be formed A top down hierarchical clustering technique 17 is adopted and improved to get a better clustering result It aims to partition the frontier candidates into several clusters which are no larger than double of the robot s wide and the number of the clusters is as small as possible The reachable cell nearest to the centroid of a divided partition is considered as a frontier The corresponding detailed algorithm is shown below The Optimal K means Clustering Algorithm Input Frontier candidates C Point clouds all Output Frontiers 1 for i jC a do 2 points of in PPalli j a 3 end for 4 QP clusters 5 radius radius P 6 while find radius thrd r do 7 bigQ clusters find radius Qthrd clustersr 8 for bigQ clusters do 9 ii 1 Bi Partition 10 QQ clustersclusters 11 radiusradiusradius 12 i1 QQi clustersclusters 13 1 radius rad ius ii radiusradius 14 End for 15 End while 16 Centroids centroid Q clusters 17 centr Centroids gridIndex 18 for centri j a do 19 distance C i j mina 20 Frontiers Frontiers 21 end for 22 return Frontiers B Choose the sub target With multiple frontiers found the sub target can be selected from them In this paper the sub target is chosen by evaluating the travel cost from the current location of the robot to the frontier A Graph based search method A algorithm 26 is used for the path planning task which generates an optimal path with additional travel cost for the target assigned When the traversability map has the form of the extended traversability map in Fig 1 the travel cost at a candidate cell is not only determined by itself but also by its parent cell Therefore the travel cost is i ji ji ji j m n f aghF 11 where i j ais a cell defined in Section 2 i j f ais the estimated total distance cost to the cell i j gis the actual distance cost from the start cell to the current cell i j a i j h is the estimated distance cost from the current cell i j a to the target cell i j m n F is the traversability index determined by the direction that the robot travels from the parent cell m n a to the current cell i j a which can be found in the extended traversability map For each of the frontier the A algorithm gives an optimal path and its corresponding travel cost The frontier with minimal travel cost is then chosen to be the sub target minTravelCost Frontiers Sub target 12 where TravelCost is the optimal travel cost to get to the candidate position with A algorithm 4888 IV EXPERIMENTAL RESULTS In this section the proposed algorithm for autonomous exploration is tested in an outdoor env