System for obstacle avoidance path planning for multiple-degree-of-freedom mechanism

• US 5,502,638 A
• Filed: 02/08/1993
• Issued: 03/26/1996
• Est. Priority Date: 02/10/1992
• Status: Expired due to Term

• Current Assignee: Honda Giken Kogyo Kabushiki Kaisha (Honda Motor Company)
• Original Assignee: Honda Giken Kogyo Kabushiki Kaisha (Honda Motor Company)
• Inventors: Takenaka, Toru
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US08/014,611
• Time in Patent Office: 1,142 Days
• Field of Search: 364/167.01, 364/424.01, 364/424.02, 364/443, 364/444, 364/449, 364/461, 318/616, 395/90
• US Class Current: 701/87
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

In a system for obstacle avoidance path finding for a multiple-degree-of-freedom mechanism such as a mobile robot moving from a starting point to a goal while avoiding obstacles. Obstacles are defined to be a virtual space having a continuous drag coefficient that increases with increasing proximity to the obstacles. A path is determined on the basis of the variational principle as the extreme for a functional such as time required for the mobile robot'"'"'s movement. Since the viscous drag coefficient is greatest at the obstacles, the determined path does not go through the obstacles thereby avoiding the obstacles. Moreover, since the path is determined on the variational principle, the time required for the movement is adopted as the functional, the determined path will locally be that of minimum time.

Claims

1. A system for obstacle avoidance path planning for a multiple-degree-of-freedom mechanism moving from a predetermined point to a goal avoiding an obstacle, comprising:

first means for defining a viscous drag coefficient distribution on the obstacle;

second means for describing a time required for the mechanism to move from the predetermined point to the goal with a functional, using the viscous drag coefficient distribution;

third means for determining a path on the basis of the variational principle with the viscous drag coefficient distribution such that the functional has an extreme value; and

fourth means for driving the mechanism along the determined path.

2. A system according to claim 1, wherein said third means includes:

means for establishing a condition for avoiding the obstacle in advance;

and said third means determines the path in accordance with the established condition.

3. A system according to claim 2, wherein the condition is the characteristics of locus and said third means determines the path by comparing it with the characteristics of locus.

4. A system according to claim 1, wherein said first means defines the viscous drag coefficient distribution such that it is largest at the distribution'"'"'s defined obstacle and continuously decreases with decreasing proximity thereto.

5. A system according to claim 4, wherein said first means defines the viscous drag coefficient distribution on the obstacle which increases with sequential trials of movement.

6. A system according to claim 1, wherein the drag coefficient distribution is also defined on the mechanism and moves with the mechanism.

7. A system according to claim 6, wherein said first means defines the viscous drag coefficient distribution to provide the mechanism with an inertial force.

8. A system according to claim 6, wherein said first means defines the viscous drag coefficient distribution with anisotropy such that a direction of the mechanism'"'"'s movement is limited.

9. A system according to claim 1, wherein the obstacle is a known-obstacle.

10. A system according to claim 1, wherein the obstacle is expressed in a two-dimensional environment.

11. A system according to claim 1, wherein the obstacle is expressed in a three-dimensional environment.

12. A system according to claim 1, wherein the obstacle is expressed in an environment having a time axis.

13. A system for obstacle avoidance path planning for a multiple-degree-of-freedom mechanism moving from a predetermined point to a goal and avoiding an obstacle, comprising:

first means for defining a viscous drag coefficient distribution on the obstacle and the predetermined point;

second means for describing a time required for the mechanism to move from the predetermined point to the goal with a functional using the viscous drag coefficient distribution;

third means for determining a path on the basis of the variational principle with the viscous drag coefficient distribution such that the functional has an extreme value; and

fourth means for driving the mechanism along the determined path.

14. A system according to claim 13, wherein said third means includes:

means for establishing a condition for avoiding the obstacle in advance;

and said third means determines the path in accordance with the established condition.

15. A system according to claim 14, wherein the condition is the characteristics of the locus and said second means determines the path by comparing it with the characteristics of the locus.

16. A system according to claim 13, wherein said first means defines the viscous drag coefficient distribution such that it is largest at the distribution'"'"'s defined obstacle and predetermined point and continuously decreases with decreasing proximity thereto.

17. A system according to claim 16, wherein said first means defines the viscous drag coefficient distribution at least on the obstacle which increases with sequential trials of movement.

18. A system according to claim 13, wherein said first means defines the viscous drag coefficient distribution limiting an initial direction of the mechanism'"'"'s movement.

19. A system according to claim 13, wherein said first means defines the viscous drag coefficient distribution imparted with anisotropy limiting an initial direction of the mechanism'"'"'s movement.

20. A system according to claim 13, wherein the obstacle is a known obstacle.

21. A system according to claim 13, wherein the obstacle is expressed in a two-dimensional environment.

22. A system according to claim 13, wherein the obstacle is expressed in a three-dimensional environment.

23. A system according to claim 13, wherein the obstacle is expressed in an environment having a time axis.

24. A system according to claim 13, wherein said first means defines the viscous drag coefficient distribution on the obstacle, the predetermined point and the goal.

25. A system according to claim 13, wherein said first means defines the viscous drag coefficient distribution on the obstacle, the predetermined point, the goal and the mechanism.