ROUTE PLANNING METHOD, ROUTE PLANNING DEVICE AND AUTONOMOUS MOBILE DEVICE

• US 20110166737A1
• Filed: 08/24/2009
• Published: 07/07/2011
• Est. Priority Date: 09/03/2008
• Status: Active Grant

• Current Assignee: Murata Machinery Limited (Muratec)
• Original Assignee: Murata Machinery Limited (Muratec)
• Inventors: Shitamoto, Hideo, Tanaka, Shoji
• Granted Patent: US 8,515,612 B2
• Time in Patent Office: Days
• US Class Current: 701/25
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A route planning device that is capable of comprehending, in advance, a route clearance at a pass-through point on a planned travel route, includes a global map acquisition unit arranged to generate a global map showing an obstacle area in which an obstacle exists, an extended area generation unit arranged to generate an extended obstacle area and three extended area by extending stepwise an outline of the obstacle area contained in the global map, an integrated map generation unit arranged to generate an integrated map by superposing for integration of the extended obstacle area with the three extended areas; a movable area extraction unit arranged to extract a movable area from the integrated map and thinning the same, and a route planning unit arranged to acquire a route clearance at a sub goal according to the extended areas on the integrated map to which the sub goal on the travel route belongs, upon planning the travel route from the thinned movable area.

Claims

1-22. -22. (canceled)

23. A route planning method of planning a travel route to be used by an autonomous mobile device, which travels along the travel route, before the autonomous mobile device travels autonomously, the method comprising:

an environmental map acquisition step of acquiring an environmental map showing an obstacle area in which an obstacle exists;

an extended area generation step of generating a plurality of extended areas by extending stepwise an outline of the obstacle area contained in the environmental map acquired in the environmental map acquisition step;

an integrated map generation step of generating an integrated map by superposing and integrating the plurality of extended areas generated in the extended area generation step;

a movable area extraction step of extracting a movable area from the integrated map generated in the integrated map generation step; and

a route planning step of planning a travel route from the movable area extracted in the movable area extraction step and acquiring a route clearance at a pass-through point according to an extended area on the integrated map to which the pass-through point on the travel route belongs.

24. The route planning method according to claim 23, wherein, in the extended area generation step, the outline of the obstacle area is extended in an amount corresponding to a radius of the autonomous mobile device, and the outline of the extended obstacle area is additionally extended stepwise in a predetermined range of extension.

25. The route planning method according to claim 24, wherein the predetermined range of extension is a radius of the autonomous mobile device.

26. A route planning device for planning a travel route to be used by an autonomous mobile device, which travels along the travel route, before the autonomous mobile device travels autonomously, the route planning device comprising:

an environmental map acquisition unit arranged to acquire an environmental map showing an obstacle area in which an obstacle exists;

an extended area generation unit arranged to generate a plurality of extended areas by extending stepwise an outline of the obstacle area contained in the environmental map acquired by the environmental map acquisition unit;

an integrated map generation unit arranged to generate an integrated map by superposing and integrating the plurality of extended areas generated by the extended area generation unit;

a movable area extraction unit arranged to extract a movable area from the integrated map generated by the integrated map generation unit; and

a route planning unit arranged to plan a travel route from the movable area extracted by the movable area extraction unit and acquire a route clearance at a pass-through point according to an extended area on the integrated map to which the pass-through point on the travel route belongs.

27. The route planning device according to claim 26, wherein the extended area generation unit extends the outline of the obstacle area in an amount corresponding to a radius of the autonomous mobile device, and additionally extends stepwise the outline of the extended obstacle area in a predetermined range of extension.

28. The route planning device according to claim 27, wherein the predetermined range of extension is a radius of the autonomous mobile device.

29. An autonomous mobile device which travels along a planned travel route in an ambient environment, the device comprising the route planning device according to claim 26.

30. A route planning device for planning a travel route to be used by an autonomous mobile device, which travels along the travel route, before the autonomous mobile device travels autonomously, the device comprising:

an environmental map acquisition unit arranged to acquire an environmental map showing an obstacle area in which an obstacle exists;

a movable area extraction unit arranged to extract a movable area from the environmental map acquired by the environmental map acquisition unit and thinning the extracted movable area;

a route planning unit arranged to plan a travel route from the thinned movable area extracted by the movable area extraction unit by searching for the shortest route to the destination;

a linearization unit arranged to linearize the travel route planned by the route planning unit without interfering with the obstacle area; and

a smoothing unit arranged to smooth the travel route linearized by the linearization unit without interfering with the obstacle area.

31. The route planning device according to claim 30, wherein the linearization unit extracts two points on the travel route, connects the two points with a straight line, and, when the connected straight line does not interfere with the obstacle area, re-sets the straight line as a travel route which connects the two points.

32. The route planning device according to claim 31, wherein, when the straight line connecting the two points does not interfere with the obstacle area, the linearization unit fixes one point of the two points, and sequentially changes the other point of the two points to a point that is more distant from the one point until the straight line connecting the two points interferes with the obstacle area.

33. The route planning device according to claim 31, wherein the linearization unit linearizes the travel route repeatedly from one end point to the other end point of the travel route.

34. The route planning device according to claim 30, wherein the smoothing unit extracts a point on the linearized travel route and two points on the linearized travel route sandwiching the point, connects the two points with a straight line, and, when the connected straight line does not interfere with the obstacle area, re-sets the straight line as a travel route which connects the two points.

35. The route planning device according to claim 34, wherein, when the straight line connecting the two points does not interfere with the obstacle area, the smoothing unit fixes the point sandwiched by the two points, and sequentially changes each of the two points to a point that is more distant from the point until the straight line connecting the two points interferes with the obstacle area.

36. The route planning device according to claim 34, wherein the smoothing unit smoothes the travel route repeatedly from one end point to the other end point of the travel route.

37. The route planning device according to claim 34, wherein the smoothing unit smoothes the travel route when an angle formed by the extracted three points is not greater than a certain value that is set forth according to mobility of the autonomous mobile device.

38. The route planning device according to claim 30, wherein the movable area extraction unit generates an extended obstacle area by extending the outline of the obstacle area on the environmental map in an amount corresponding to a radius of the autonomous mobile device, and extracts an area excluding the extended obstacle area as the movable area.

39. An autonomous mobile device which travels along a planned travel route in an ambient environment, the device comprising the route planning device according to claim 30.

40. An autonomous mobile device, comprising:

an environmental map acquisition unit arranged to acquire an environmental map showing an obstacle area in which an obstacle exists;

a route planning unit arranged to plan a travel route from the environmental map acquired by the environmental map acquisition unit;

a route clearance acquisition unit arranged to acquire a route clearance of the travel route planned by the route planning unit;

a moving unit arranged to move a autonomous mobile device;

a self location detector arranged to detect a self location; and

a travel controller programmed and arranged to acquire the route clearance at the self location obtained from the self location detected by the self location detection unit and the route clearance acquired by the route clearance acquisition unit, and to control the moving unit according to the route clearance at the self location.

41. The autonomous mobile device according to claim 40, further comprising a storage unit arranged to store the travel route planned by the route planning unit and the route clearance acquired by the route clearance acquisition unit;

wherein

the travel control unit acquires the route clearance at the self location obtained from the self location detected by the self location detection unit and the route clearance stored in the storage unit.

42. The autonomous mobile device according to claim 40, wherein the travel controller sets a travel speed of the autonomous mobile device according to the route clearance at the self location, and controls the moving unit based on the travel speed.

43. The autonomous mobile device according to claim 40, wherein the travel controller includes an obstacle avoidance control unit arranged to set an avoidance force to avoid an obstacle according to the route clearance at the self location, and control the moving unit based on the avoidance force set by the obstacle avoidance control unit.

44. An autonomous mobile device which plans a travel route to a destination before traveling autonomously and which travels along the travel route, the device comprising:

an environmental map acquisition unit arranged to acquire an environmental map showing an obstacle area in which an obstacle exists;

an extended area generation unit arranged to generate a plurality of extended areas by extending stepwise an outline of the obstacle area contained in the environmental map acquired by the environmental map acquisition unit;

an integrated map generation unit arranged to generate an integrated map by superposing and integrating the plurality of extended areas generated by the extended area generation unit;

a movable area extraction unit arranged to extract a movable area from the integrated map generated by the integrated map generation unit;

a route planning unit arranged to plan a travel route from the movable area extracted by the movable area extraction unit;

a route clearance acquisition unit arranged to acquire a route clearance at a pass-through point according to an extended area on the integrated map to which the pass-through point on the travel route planned by the route planning unit belongs;

a moving unit arranged to move a autonomous mobile device;

a self location detector arranged to detect a self location; and

a travel controller programmed and arranged to acquire the route clearance at the self location obtained from the self location detected by the self location detector and the route clearance acquired by the route clearance acquisition unit, and control the moving unit according to the route clearance at the self location.

45. The autonomous mobile device according to claim 44, further comprising a storage unit arranged to store the travel route planned by the route planning unit and the route clearance acquired by the route clearance acquisition unit;

wherein

the travel controller detects, from a target pass-through point sequence on the travel route, one target pass-through point which coincides with or is closest to the self location, or detects a plurality of target pass-through points contained in a certain range from the self location, and acquires the route clearance which is stored in correspondence with the detected target pass-through point.

46. The autonomous mobile device according to claim 44, wherein the route clearance is comprehended from an integrated value on the integrated map, and is represented as being closer to an obstacle in an area having a greater integrated value and as being distant from an obstacle in an area having a smaller integrated value;

and

the travel controller sets a target travel speed so that the travel speed of the autonomous mobile device becomes slower as the route clearance at the self location becomes smaller, and controls the moving unit based on the target travel speed.

47. The autonomous mobile device according to claim 44, wherein the route clearance is comprehended from an integrated value on the integrated map, and is represented as being closer to an obstacle in an area having a greater integrated value and as being distant from an obstacle in an area having a smaller integrated value;

and

the travel controller includes an obstacle avoidance control unit arranged to set avoidance force of avoiding the obstacle moderately as the route clearance at the self location becomes smaller, and controls the moving unit based on the avoidance force set by the obstacle avoidance control unit.