Method of and apparatus for determining optimum delivery route for articles

• US 6,246,931 B1
• Filed: 06/22/1999
• Issued: 06/12/2001
• Est. Priority Date: 06/24/1998
• Status: Expired due to Fees

• Current Assignee: Honda Giken Kogyo Kabushiki Kaisha (Honda Motor Company)
• Original Assignee: Honda Giken Kogyo Kabushiki Kaisha (Honda Motor Company)
• Inventors: Shinogi, Yoshihisa
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Donnelly, Arthur D.
• Application Number:
  US09/337,273
• Time in Patent Office: 721 Days
• Field of Search: 701/202, 701/201, 701/24, 701/25, 701/26, 701/208, 701/23, 319/580, 180/167, 180/8, 180/168, 340/941
• US Class Current: 701/24
• CPC Class Codes: B25J 9/161 Hardware, e.g. neural networks, fuzzy logic, interfaces, processor

Abstract

A delivery route for an article is automatically generated without the need for training a delivery robot for its path of movement. A spatial structure in which the delivery robot is movable is described from a delivery start position to a delivery destination position according to a quadtree method, and stored as a map in a memory. A safety connection weight calculator calculates the weight of a connection relative to the safety of a direction of delivery, by referring to the stored map, and an objective direction connection weight calculator calculates the weight of an objective direction connection taking into account a shortest distance in the direction of delivery, by referring to the stored map. A preceding direction of delivery is considered from an output of a neutral network processor, and established in the neutral network processor via a feedback connection weight setting unit. The neutral network processor autonomously generates optimum delivery route data according to the error backpropagation learning algorithm.

Claims

1. A method of determining an optimum delivery route for delivering an article from a delivery start position to a delivery destination position with a delivery robot capable of lifting the workpiece with an end effector at the delivery start position, delivering the workpiece in forward, backward, left, and right directions, and lowering the workpiece at the delivery destination position, comprising the steps of:

describing a spatial structure in which the delivery robot is movable, from said delivery start position to said delivery destination position according to a quadtree method, and storing the described spatial structure as a map; and

determining an optimum delivery route according to neutral network processing by referring to said map taking into account the safety of a direction of delivery and a shortest delivery distance.

2. A method according to claim 1, wherein the optimum delivery route is determined taking into account the safety of the direction of delivery, the shortest delivery distance, and a preceding direction of delivery.

3. A method according to claim 1, wherein a unit delivery distance for the delivery robot in said map is selected to the length of one side of a rectangular parallelepiped that circumscribes the article.

4. A method according to claim 3, wherein for determining an optimum delivery route from a present position to a next delivery position for the article, the safety of the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 1 representing that no obstacle is present in three unit delivery distances ahead in a present direction of travel, with the values from 0.5 to 0.8 representing that an obstacle is present in the second unit delivery distance ahead in the present direction of travel, and the value 0 representing a direction of delivery with an obstacle present therein, and the shortest delivery distance in the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 1 representing that the distance from said present position to said delivery destination position is shortest in the direction of travel, and with the values from 0.5 to 0.8 representing that the distance from said present position to said delivery destination position is second shortest in the direction of travel.

5. A method according to claim 4, wherein the safety of the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 0.7 representing that an obstacle is present in the second unit delivery distance ahead in the present direction of travel, and the shortest delivery distance in the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 0.7 representing that the distance from said present position to said delivery destination position is second shortest in the direction of travel.

6. An apparatus for determining an optimum delivery route for delivering an article from a delivery start position to a delivery destination position with a delivery robot capable of lifting the workpiece with an end effector at the delivery start position, delivering the workpiece in forward, backward, left, and right directions, and lowering the workpiece at the delivery destination position, comprising:

a map generator for describing a spatial structure in which the delivery robot is movable, from said delivery start position to said delivery destination position according to a quadtree method, and generating a map representing the described spatial structure;

storage means for storing the generated map;

a safety connection weight calculator for calculating the weight of a safety connection taking into account the safety of a direction of delivery, by referring to the map stored in said storage means;

an objective direction connection weight calculator for calculating the weight of an objective direction connection taking into account a shortest distance in the direction of delivery, by referring to the map stored in said storage means;

a neural network processor; and

a feedback connection weight setting unit for storing an output from said neural network processor as the weight of a feedback connection for taking into account a preceding direction of delivery;

said neural network processor comprising means for determining an optimum delivery route according to a propagation learning algorithm based on said weight of the safety connection, said weight of the objective direction connection, and said weight of the feedback connection.

7. An apparatus according to claim 6, wherein a unit delivery distance for the delivery robot in said map is selected to the length of one side of a rectangular parallelepiped that circumscribes the article.

8. An apparatus according to claim 6, wherein for determining an optimum delivery route from a present position to a next delivery position for the article, the safety of the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 1 representing that no obstacle is present in three unit delivery distances ahead in a present direction of travel, with the values from 0.5 to 0.8 representing that an obstacle is present in the second unit delivery distance ahead in the present direction of travel, and the value 0 representing a direction of delivery with an obstacle present therein, and the shortest delivery distance in the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 1 representing that the distance from said present position to said delivery destination position is shortest in the direction of travel, and with the values from 0.5 to 0.8 representing that the distance from said present position to said delivery destination position is second shortest in the direction of travel.

9. An apparatus according to claim 8, wherein the safety of the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 0.7 representing that an obstacle is present in the second unit delivery distance ahead in the present direction of travel, and the shortest delivery distance in the direction of delivery is standardized and described in a range of values from 0 through 1, with the value 0.7 representing that the distance from said present position to said delivery destination position is second shortest in the direction of travel.

10. An apparatus according to claim 6, wherein said weight of the safety connection, said weight of the objective direction connection, and said weight of the feedback connection, which are supplied as inputs to said neutral network processor, are established with respect to each of forward, left, right, and backward directions, and an output of said neutral network processor is determined with respect to each of forward, left, right, and backward directions.

11. An apparatus according to claim 6, wherein said weight of the safety connection, said weight of the objective direction connection, and said weight of the feedback connection, which are supplied as inputs to said neutral network processor, are established with respect to each of forward, left, right, and backward directions, and an output of said neutral network processor is determined with respect to each of forward, left, right, backward directions, goal arrival, and emergency avoidance.