Node map system and method for vehicle

• US 4,821,192 A
• Filed: 11/28/1986
• Issued: 04/11/1989
• Est. Priority Date: 05/16/1986
• Status: Expired due to Fees

• Current Assignee: E.T.M. Realty Trust
• Original Assignee: Denning Mobile Robotics, Inc.
• Inventors: Kadonoff, Mark B., Taivalkoski, Amy L.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/936,092
• Time in Patent Office: 865 Days
• Field of Search: 364/424, 364/436, 364/449, 364/513, 180/167, 180/168, 180/169, 180/211, 180/212
• US Class Current: 701/25
• CPC Class Codes: B25J 19/026 Acoustical sensing devices
• CPC Class Codes: B25J 9/0003 Home robots, i.e. small robots for domestic use
• CPC Class Codes: G05D 1/0221 involving a learning process
• CPC Class Codes: G05D 1/0225 involving docking at a fixed facility, e.g. base station or loading bay parking aids B62D15/027
• CPC Class Codes: G05D 1/0234 using optical markers or beacons optical beacons per se G01S1/70
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/027 comprising intertial navigation means, e.g. azimuth detector inertial navigation G01C21/16; inertial navigation combined with non-inertial navigation instruments G01C21/165
• 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 mapping system and method which establish a number of navigation nodes and paths among them for a vehicle in an environment to be navigated by directing the vehicle to a selected location in the environment, designating that location as a first node, identifying the initial direction of a path to a second node such as by locating a navigation beacon proximate the second node, and moving the vehicle in the initial direction from the first node while measuring distance travelled along the path to the second node. This system and method further include defining the second node by at least the distance travelled along the path and by the initial path direction.

Claims

1. A mapping system for establishing a number of navigation nodes, each proximate a navigation beacon, and interconnecting paths in an environment to be navigated by a vehicle having a drive system, comprising:

means for directing the vehicle to a selected location in the environment and designating that location as a first node;

means for locating the initial direction of a path from said first node to a second node relative to a beacon proximate said second node;

means, responsive to said means for locating, for commanding the drive system to move the vehicle along said path in said initial direction from said first node;

means for measuring distance travelled by the vehicle along said path from said first to said second node; and

means, responsive to said means for measuring, for defining said second node by at least the distance travelled along said path between said first and second nodes and by said initial direction.

2. The system of claim 1 in which said means for locating includes azimuthal detector means for sensing a navigation beacon and for resolving the azimuthal angle between a reference direction for the vehicle and the direction of the beacon relative to the vehicle.

3. The system of claim 2 in which said means for commanding includes means, responsive to said azimuthal detector means, for turning said vehicle by said vehicle-beacon azimuthal angle.

4. The system of claim 2 in which said means for locating further includes means for moving said azimuthal detector means to search for the navigation beacon.

5. The system of claim 4 in which said means for moving searches for a navigation beacon having a particular identification code.

6. The system of claim 1 further including means for monitoring the orientation of the vehicle relative to the environment.

7. The system of claim 6 further including means for substantially continuously resolving, while the vehicle is travelling along said path, the orientation of the vehicle relative to a feature in the environment and for updating said means for monitoring.

8. The system of claim 7 in which said means for resolving defines vehicle orientation relative to the beacon.

9. The system of claim 1 further including means for halting the vehicle at said second node.

10. The system of claim 9 in which said means for halting includes halt input means for operator input of a halt command.

11. The system of claim 1 in which said means for halting includes altitudinal detector means for sensing a navigation beacon and for resolving the altitudinal angle between the beacon and the vehicle.

12. The system of claim 11 in which said means for halting further includes means for comparing the altitudinal angle with a predetermined angle and for arresting travel of the vehicle when they match.

13. The system of claim 1 in which said means for directing includes means for selecting said second node as the location from which a third node is to be established.

14. The system of claim 1 in which said means for directing includes input means for operator input of said selected location for said first node.

15. The system of claim 14 in which said means for directing further includes guidance input means for operator guidance of the vehicle to said selected location.

16. The system of claim 1 further including task input means for operator input of task commands defining actions to be performed by the vehicle along that path.

17. The system of claim 1 further including node task means for operator input of task commands defining actions to be performed by the vehicle at said second node.

18. The system of claim 1 in which said means for defining includes means for storing said initial path direction and said path distance.

19. A mapping system for establishing a number of navigation nodes and paths among them in an environment to be navigated by a vehicle having a drive system, comprising:

means for directing the vehicle to a selected location in the environment and designating that location as a first node;

means for identifying the initial direction of a path from said first node to a second node;

means for commanding the drive system to move the vehicle in said initial direction from said first node;

means for measuring distance travelled by the vehicle along said path; and

means, responsive to said means for measuring, for defining said second node by at least the distance travelled along said path and by said initial direction.

20. The system of claim 19 in which said means for identifying includes means for determining the azimuthal angle by which the vehicle must turn to face said initial direction.

21. The system of claim 20 in which said means for determining includes angle input means for operator input of said azimuthal angle.

22. A mapping system for establishing a number of navigation nodes and paths among them in an environment to be navigated, comprising:

a vehicle having a drive system including a drive motor and a steering system;

means for directing said vehicle to a selected location in the environment and designating that location as a first node;

means for identifying the initial direction of a path to a second node;

means for commanding said drive system to move said vehicle in said initial direction from said first node;

means for measuring distance travelled by said vehicle along said path; and

means, responsive to said means for measuring, for defining said second node by at least the distance travelled along said path and by said initial direction.

23. The system of claim 22 in which said means for measuring distance includes drive encoder means, responsive to said drive motor, for determining distance travelled by said vehicle.

24. The system of claim 22 in which said means for identifying includes means for determining the azimuthal angle by which said vehicle must turn to face said initial direction.

25. The system of claim 24 in which said means for determining includes azimuthal detector means for sensing a navigation beacon and for resolving the azimuthal angle between said vehicle and the beacon.

26. The system of claim 25 in which said means for commanding includes means, responsive to said azimuthal detector means and said steering system, for turning said vehicle by said vehicle-beacon azimuthal angle.

27. The system of claim 22 in which said vehicle is a mobile robot.

28. A mapping system for establishing a number of navigation nodes and paths among them in an environment to be navigated by a vehicle having a drive system, comprising:

input means for operator input to designate a selected location in the environment as a first node, to identify the initial direction of a path to a second node, and to halt the vehicle at said second node;

means for commanding the drive system to move the vehicle in said initial direction from said first node;

means for measuring distance travelled by the vehicle along said path; and

means, responsive to said means for measuring, for defining said second node by at least the distance travelled along said path and by said initial direction.

29. A system for navigating a vehicle from node to node utilizing a map, stored in the vehicle, which defines a plurality of navigation nodes in relation to each other, comprising:

means for directing the vehicle to a first node recorded in the map;

means for referencing the map to identify the known initial direction of a path from said first node to a second node proximate a navigation beacon and to identify the known distance of said path;

detector means for sensing said navigation beacon and for resolving at least the azimuthal angle between a reference direction for the vehicle and the direction of the beacon relative to the vehicle; and

means, responsive to said means for referencing and said detector means, for commanding the vehicle to proceed in said initial direction and to navigate along said path to said second node for said known distance.

30. The system of claim 29 in which said means for referencing identifies said initial direction based on a predetermined azimuthal angle from said first node toward said beacon proximate said second node.

31. The system of claim 29 in which said detector means also resolves th altitudinal angle between the vehicle and the beacon.

32. The system of claim 31 in which said means for referencing identifies said second node by a predetermined altitudinal angle observalbe at said second node.

33. The system of claim 32 in which said means for commanding includes means, responsive to said detector means, for halting the vehicle when the resolved altitudinal angle matches said predetermined altitudinal angle.

34. The system of claim 29 in which said beacon includes means for producing energy in a coded signal which uniquely identifies that beacon, and said means for referencing retrieves from the map the identification code for that beacon.

35. The system of claim 34 in which said detector means includes:

a multisector sensor for sensing a signal emitted by said beacon;

means, responsive to said sensor, for generating a code data signal representative of said coded signal; and

means, responsive to said sensor sectors, for generating an angle data signal representative of the angle from said sensor to said beacon in at least the azimuthal dimension.

36. The system of claim 29 further including planner means for designating successive nodes to visit and for providing said successive nodes to said means for directing.

37. A method of establishing a number of navigation nodes and paths among them for a vehicle in an environment to be navigated, comprising:

generating signals for causing the vehicle to move to a selected location in the environment;

recording, within memory of the vehicle, that location as a first node;

generating direction signals for identifying the initial direction of a path to the second node;

moving the vehicle in the initial direction from the first node while measuring distance traveled along the path;

generating node-defining signals for defining the second node by at least the distance traveled along the path and by the initial path direction; and

repeatedly generating direction signals, moving, and generating node-defining signals until a desired numbe of nodes and paths are established.

38. The method of claim 37 further including establishing a return path to said first node.

39. The method of claim 37 further including recording the established nodes to form a map of the environment.

40. The method of claim 39 further including assigning tasks for the vehicle to perform along each path.

41. The method of claim 39 further including assigning tasks for the vehicle to perform at each node.

42. The method of claim 37 in which generating signals for causing the vehicle to move includes sensing a navigation beacon proximate the selected location to be recorded as a first node.

43. The method of claim 42 in which generating direction signals includes sensing a second beacon proximate the second node.

44. The method of claim 37 in which generating signals for causing the vehicle to move includes entering commands through an input device connected to the vehicle to cause the vehicle to move to the selected location.

45. The method of claim 44 in which generating direction signals includes entering direction commands through the input device to identify the initial direction.

46. A method of establishing navigational paths for a mobile robot traveling within an environment among navigation nodes proximate navigation beacons, comprising:

directing the robot to a position to be designated as a navigation node;

recording the location of the position of the robot within the environment as a first node;

instructing the robot to search for and head toward a beacon proximate a second position; and

recording information defining the location of the robot at the second position as a second node within the environment.

47. The method of claim 46 in which the information defining the location of the second node includes the azimuthal distance of the beacon from the path and the path distance to the second node.

48. The method of claim 46 in which the information defining the location of the second node includes the altitudinal angle of the beacon from the second node.