Field of the Invention

The present invention is in the field of map exploration, and specifically in the area of robotic map exploration using light detection and ranging (LIDAR).

Background of the Invention

Robots with LIDAR are very common nowadays. However, all of the robots rely on human beings to guide them through the maps, while the LIDAR draws out the map of the area it walked by. The underlying reason for robots to rely on human beings is that it does not have a coordinate to reference to until it finishes drawing the map.

There are some vacuum cleaning robots out there that use an "always turn left" methodology to try to draw out an indoor map. Nevertheless, those methods can be easily trapped by rooms or pockets of specific shapes.

The present invention aims to provide a fully automatic method of map exploration and provide algorithms that can tackle special circumstances.

Summary of the Invention

In one aspect, the present invention discloses a map exploration method comprising the steps: scanning the surrounding area with a LIDAR having a scanning radius A; defining the area which is reachable by the LIDAR as a first layer; defining the circular area centred at the LIDAR with radius B as a second layer, where B is smaller than A; and moving the LIDAR to different locations until the second layer overwrites the first layer; wherein a map is drawn while moving the LIDAR.

In one embodiment, the map exploration method further comprises: randomly selecting multiple destination positions in the first layer but outside the second layer; calculating distances between the multiple destination positions and the current position of the LIDAR; moving the LIDAR to the destination position with the longest distance from the current position; and performing iterations until the second layer overwrites the first layer.

In a further embodiment, the map is a 2D map and walls and obstacles are drawn by solid lines.

In yet another embodiment, the map exploration method further comprises: defining the area behind a glass wall that can be detected by the LIDAR but cannot be reached by a moving unit installed with the LIDAR as a trap; driving the moving unit at least 3 times to get inside the trap; storing stopping positions of the moving unit; drawing a solid line across the stopping positions on the map; and deleting the trap from the map. In a further embodiment, the map exploration method further comprises triggering an enclosure detection algorithm when the second layer overwrites the first layer. The enclosure detection algorithm comprising: finding out vertices of walls; and checking whether there exists a path that traverses each vertex exactly once such that the path begins and ends at the same vertex.

In a further embodiment, the moving unit is a robot, a drone or an automobile.

In another aspect, the present invention is a system for map exploration. The system comprises a LIDAR having a scanning radius A for scanning surrounding area; a moving unit for carrying the LIDAR; and a processor. The processor performs the following steps: defining the area which is reachable by the LIDAR as a first layer; defining the circular area centred at the LIDAR with radius B as a second layer, where B is smaller than A; driving the moving unit to different locations until the second layer overwrites the first layer; and drawing a map while driving the moving unit.

In an exemplary embodiment, the processor further performs the steps: randomly selecting multiple destination positions in the first layer but outside the second layer; calculating distances between the multiple destination positions and the current position; driving the moving unit to the destination position with the longest distance from the current position; and performing iterations until the second layer overwrites the first layer.

In a further embodiment, the processor further comprises: defining the area behind a glass wall that can be detected by the LIDAR but cannot be reached by the moving unit as a trap; driving the moving unit at least 3 times to get inside the trap; storing stopping positions of the moving unit; drawing a solid line across the stopping positions on the map; and deleting the trap from the map.

In yet another embodiment, the system for map exploration further comprises an enclosure detection module which is triggered when the second layer overwrites the first layer, the enclosure detection module comprises: finding out vertices of walls; and checking whether there exists a path that traverses each vertex exactly once such that the path begins and ends at the same vertex.

The present invention has many advantages. For example, the map exploration is fully automatic. No human interference is needed. In addition, exceptions are properly handled such that the map generated is accurate and the map is fully explored.

Brief Description of the Drawings

The accompanying drawings incorporated in specification, illustrate several embodiments of the disclosed method and system and together with the description, serve to explain the principles of the disclosed method and system.

Figure 1 is a block diagram of the map exploration system in one embodiment of the present invention.

Figure 2 is a flowchart of the algorithm of the present invention.

Figure 3 is a map drawn by the system when the LIDAR is in a first location.

Figure 4 is a map drawn by the system when the LIDAR is in a second location.

Figure 5 shows the maps drawn by the system when the LIDAR is in a third location and a fourth location.

Figure 6 is a schematic diagram of a trap with a straight boundary.

Figure 7 is a schematic diagram of a trap with a boundary that is not straight.

Figure 8 is a diagram for illustration of the enclosure detection algorithm.

Detailed Description of the Invention

The disclosed method and system can be understood more readily by reference to the following detailed description of particular embodiments and the Example included therein.

Referring to figure 1, the system comprises several crucial components, i.e. a LIDAR 10, a moving unit 20 and a processor 30. The LIDAR 10 acts as a SLAM (Simultaneous localization and mapping) sensor. It sends out Infra-red light and detects their time of flight to draw all the obstacles within its line of sight. As the moving unit 20 moves around the premise, the obstacle details will be constructed more clearly by cross referencing multiple readings of the same point on the obstacle. The processor 30 is interconnected with the LIDAR 10 and the moving unit 20. The LIDAR 10 can rotate 360 degrees and send the detected data to the processor 30 for processing. The processor 30 draws a digital map using the detected data and drives the moving unit 20 to different locations based on the surrounding environment.

The moving unit 20 can be a robot, a drone, an automobile or any other machines that are suitable for map exploration. The system can be equipped with more components for better performance. For example, a 3D camera can be added to detect optically the obstacles in front of the moving unit 20, construct an approximate size of the object and plan a path to get around them if needed. Time of flight sensors can be added in front and at the back of the moving unit 20, aiming at different angles, to provide proximity alert when they detect an obstacle.

The gist of this invention is to provide an algorithm to automatically explore unknown maps without intervention of human beings. In the following embodiment, a robot as the moving unit 20 and an indoor map are used for explanation of the working principle. Referring to figures 2, a flowchart of the algorithm is shown. In step 40, the algorithm starts. The robot can be placed in an arbitrary location in the indoor map as the starting point. The robot then uses the LIDAR 10 to scan the surrounding area in step 50. The LIDAR 10 can rotate 360°horizontally. The LIDAR 10 has a visible range from several meters to hundreds of meters, depending on the actual needs. In step 60, the start point of the robot is defined as coordinate (0, 0) and the area that is in the range of the LIDAR 10 is assigned the coordinate (x, y). The area that is invisible by the LIDAR 10 has no coordinate.

In step 70, the area reachable by the LIDAR 10 is defined as a first layer. In this embodiment, we assume the LIDAR 10 has a scanning radius A. Ideally, the first layer is a circle centred at the LIDAR 10 having a radius A when the robot is at the starting point. When the robot moves, the first layer will expand. A second layer is selected as the circular area centred at the LIDAR 10 with radius B, where B is smaller than A. B is M% of the range of the LIDAR 10. M can be defined by the user based on different requirements, the higher the percentage, the faster the map exploration. However, the faster the exploration, the less details it will draw on the map, especially in between solid objects. If more detail is desired on the map, less percentage should be used. The area that is not reached by the LIDAR 10 is defined as invisible layer. In step 80, the processor 30 draws a digital map based on the information gathered by the LIDAR 10.

Turning to figure 3, it is a map drawn by the processor 30 in an exemplary embodiment. The robot is at the starting point 160. The walls and obstacles that are reached by the LIDAR 10 are drawn by solid lines. In figure 3, the first layer 130 has greater area than the second layer 140. There are a lot of walls and obstacles, and thus the first layer 130 does not look like a circle. However, the second layer 140 looks like a circle because the vision is not blocked by walls. The area behind the walls is not reachable by the LIDAR 10 and thus forms an invisible layer 150. The LIDAR 10 keeps scanning the environment continuously. If there are moving objects such as people or animals, the processor 30 will identify the coordinates of the moving objects changed, and recognize that those objects are not obstacles. Those moving objects will be deleted from the map.

Back to figure 2, the processor 30 checks if the second layer 140 overwrites the first layer 130 in step 90. If yes, the whole process is complete and it goes to step 100 for ending the algorithm. The map in this case should have been drawn completely. However, if the second layer 140 does not overwrite the first layer 130, that means the map has not been fully explored. It then goes to step 110 to determine the next destination to go. This can be done by randomly selecting multiple destination positions in the first layer 130 but outside the second layer 140. The number of destination positions can be set by the user, say 10, 20 or 30. Ranking will be given to these destination positions based on the length of the shortest path between the current position and the destination positions, the longer the path, the higher the ranking and the earlier the robot will visit this location.

The purpose of calculating this ranking is to find a point that is "furthest away" from the current position, which allows the robot to explore as much new area as possible. As in step 60, the processor 30 has the coordinate of the current position and the destination positions, i.e. (0,0) and (x, y). The shortest path can be calculated by the equation P ² - (x-O) ² +(y-O) ² , where P is the path length. Once the destination position of the highest ranking is determined, the processor 30 will drive the robot to that position, and on the way, rewrite the first layer 130 with the second layer 140. The first layer 130 will expand according to the new LIDAR reading, and the second layer 140 will expand along the path of movement of the robot. Referring to figure 4, the map is updated when the robot moves to the location 170.

As the second layer 140 almost covers a local region of the first layer 130, expansion is stopped in that direction with the wall as the boundary. The iteration is completed when there is no more first layer 130 to explore. As shown in figure 5, the map is continuously updated after a number of iterations.

There are exceptions that the algorithm has to handle. The LIDAR 10 can detect the areas behind glass walls and create first layer that cannot be reached by the robot physically. These areas are defined as traps. As in step 120 of figure 2, the processor 30 will detect traps when going to the next location. Turning to figures 6 and 7, if the robot cannot go into a specific area (the trap 180), the robot will store the coordinate it stops (crosses in the figures). The robot will try at least 3 times to get inside the trap 180, each time stopping at a different position. The processor 30 will draw a line passing through the crosses to form a glass wall, usually a straight line as shown in figure 6. If the crosses are not in a straight line, the best fit line will be drawn, as shown in figure 7. Once the glass wall is located and drawn, the trap 180 which superposes the first layer and the second layer will be deleted from the map. It is because the area outside the glass wall should be external area (such as streets) which does not form a part of the indoor map. Back to figure 2, while detecting the traps in step 120, the algorithm will go back to the step 80 for drawing the map and continue the iterations until the second layer overwrites the first layer.

Another exception to handle is sharp turn issue. There may be problems if there are sharp turns in the map, for example, a door leading to a corridor usually has 90 degree turn or more. Referring to figure 8, when the robot moves to the location 190, its line of sight is blocked by the corner 210 of the wall. The second layer and first layer are fully overlapped at this moment. The robot will stop further exploring. However, there are more area to explore, as indicated by the dotted lines 200 in figure 8. The line 220 is not a real wall.

To handle this sharp turn issue, we deploy an enclosure detection algorithm. This enclosure detection algorithm is triggered when the second layer overwrites the first layer, i.e. the enclosure detection algorithm is run before ending the map exploration process. The enclosure detection algorithm is to make sure the entire area is contagious and enclosed by at least one layer of wall. To define an enclosure, we first find out all the vertices in all the walls (black lines). The robot should have already recorded the walls during exploration and labelled some special cases such as the line 220 in figure 8 which is not recognized as a wall. The vertices are defined at the intersection of two walls. For curved walls, we define multiple vertices by dividing the curve into smaller chunks, e.g. 20cm or 30cm each. When there exists a path that traverses each vertex exactly once such that the path begins and ends at the same vertex, the path is known as a Euler circuit. If an Euler circuit exists, there is an enclosure. The whole map exploration process will be terminated. In case there is no enclosure, that means there is more unknown area to explore. A coordinate near the opening is chosen and the robot will be driven to that location for further map exploration. For example, in figure 8, the opening is near the line 220.

While the invention is explained in relation to certain embodiments, it is to be understood that various modifications thereof will be obvious to those skilled in the art upon reading the specification. Therefore, it is to be understood that the invention disclosed herein is intended to cover such modifications as fall within the scope of the appended claims.