WO2009011295A1 - 経路計画装置及び方法、コスト評価装置、並びに移動体 - Google Patents

経路計画装置及び方法、コスト評価装置、並びに移動体 Download PDF

Info

Publication number
WO2009011295A1
WO2009011295A1 PCT/JP2008/062543 JP2008062543W WO2009011295A1 WO 2009011295 A1 WO2009011295 A1 WO 2009011295A1 JP 2008062543 W JP2008062543 W JP 2008062543W WO 2009011295 A1 WO2009011295 A1 WO 2009011295A1
Authority
WO
WIPO (PCT)
Prior art keywords
node
route
cost
distance
edge
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2008/062543
Other languages
English (en)
French (fr)
Inventor
Hidenori Yabushita
Kazuhiro Mima
Yoshiaki Asahara
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Toyota Motor Corp
Original Assignee
Toyota Motor Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Toyota Motor Corp filed Critical Toyota Motor Corp
Priority to CN2008800251799A priority Critical patent/CN101755247B/zh
Priority to US12/442,234 priority patent/US8280574B2/en
Priority to EP08778064.9A priority patent/EP2172825B1/en
Publication of WO2009011295A1 publication Critical patent/WO2009011295A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
    • G05D1/0217—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory in accordance with energy consumption, time reduction or distance reduction criteria
    • G—PHYSICS
    • G05—CONTROLLING; REGULATING
    • G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
    • G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
    • G05D1/02—Control of position or course in two dimensions
    • G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
    • G05D1/0268—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means
    • G05D1/0274—Control of position or course in two dimensions specially adapted to land vehicles using internal positioning means using mapping information stored in a memory device
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem

Definitions

  • the present invention relates to a route planning device and a route planning method for selecting a route having the lowest cost among the routes from the start point to the end point included in the area represented by the dalid, and to evaluate the cost in the route planning device. And a mobile object equipped with the route planning device.
  • Patent Document 1 discloses a route planning system for a mobile robot that obtains a route from the starting point to the destination of the mobile robot.
  • This path planning system uses a geometric map of an object in the environment, and a grid map generating means for generating a grid map representing a space distribution occupied by the object that stochastically represents the position and orientation, and From the grid map using a distance corresponding to the uncertainty of the position and orientation of the object, and a polonograph generation means that generates a polonograph, and the possibility of collision with the object and the path length on the generated polonograph
  • a route search means for searching for a route from a given starting point to the destination.
  • Patent Document 1 a technique for approximating a moving space in a grid shape and evaluating the cost of a route connecting adjacent grid points is known.
  • the searched route is expressed as a set of line segments connecting adjacent grid points. Therefore, the cost of the route is evaluated as the sum of each line segment.
  • Patent Document 1 Japanese Patent Laid-Open No. 2 0 0 5-3 2 1 9 6 Disclosure of Invention
  • Fig. 7F is a diagram showing the shortest distance from the start to the goal
  • Figs. 7A to 7E are diagrams showing the shortest distance when connecting the grid points.
  • the ideal route shown in Fig. 7F is a route that connects the start and the goal with a straight line. Of the five routes shown in Figs. 7A to 7E, the ideal route is close to this ideal route. This is the route shown in However, in the conventional route search system, the route shown in FIG. 7A to FIG. 7D may be selected. For example, when the route search system is installed in Ropot, the robot may exhibit unnatural movement. There is a problem of doing.
  • the path length is expressed as a simple sum of the line segments connecting the dalid points, so that the straight line connecting any two points is recognized to be optimal. I could not. Therefore, in the conventional route search system, since the route lengths in FIGS. 7A to 7E are determined to be the same, the route shown in FIGS. 7A to 7D is generated instead of the route shown in FIG. 7E. There was something to be done. As described above, the conventional route search system has a problem that the angular resolution of the route is low and the grid route close to the ideal shortest route cannot be searched.
  • the present invention has been made to solve such a problem, and is used in a route search device, a route search method, and a route search device capable of generating an optimum route in a search space represented by a grid.
  • Another object of the present invention is to provide a cost evaluation apparatus for generating an optimal route and a mobile body equipped with a route search device. Means for solving the problem
  • a route search device is a route search device that selects a route with the lowest cost from a start point to an end point included in an area represented by a grid, and each grid is a node.
  • the cost of the edge extended from the current node of interest to the adjacent node adjacent to it is traced back a predetermined number along the path from the node of interest to the start point.
  • the selected node as the reference node,
  • a route cost calculation unit that calculates a route cost from the start point to the end point, and a route determination unit that determines a route according to the route cost.
  • the cost of the edge extended from the node of interest to the adjacent node is not simply set as the distance, but the first node from the reference node to the adjacent node (tip node located at the edge of the edge) It is calculated from the distance and the second distance from the reference node to the node of interest (the root node located at the base of the edge).
  • the reference node is a node that goes back one or more times from the node of interest, and calculates the cost of the edge based on the shortest distance between multiple nodes. Compared to the uniform cost evaluation as the edge distance, More detailed cost evaluation based on the edge pattern can be performed, and the angular resolution of the route can be improved, and a route closer to the ideal shortest distance can be generated.
  • the route cost calculation unit can calculate the route cost from the start point to the end point as the sum of the costs of the edges constituting the route.
  • the total cost of the edges calculated as (first distance minus second distance), not just the distance, can be used as the route cost.
  • the route cost calculation unit may include the first distance and the second distance.
  • the cost from the start point to the end point can be calculated with reference to a database storing the cost obtained by the distance or (the first distance minus the second distance). By referring to the database, route cost calculation can be accelerated.
  • it may further comprise a database generation unit that calculates (the first distance minus the second distance) to construct the database.
  • a database can be generated while performing a route search [0 0 1 3]
  • the cost from the starting point to an arbitrary node is the cost of the arbitrary node
  • the node having the smallest node cost among the leading nodes located at the tip of the edge is set as the target node
  • Edge generation unit that generates an edge extending to an adjacent node located at least forward, diagonally right front, and diagonally left front, and edge cost calculation that calculates or reads the first distance and the second distance from the database Z reading
  • the route cost calculation unit calculates a route cost from the start point to the adjacent node as a sum of costs of wedges constituting the route, and the route determination unit determines that the adjacent node is the end point. In this case, it is possible to select a route having the minimum cost from the start point to the end point.
  • An edge is generated from the node of interest, the cost of the edge is obtained, and the sum of the costs of the edges constituting the route can be obtained as the route cost.
  • the edge generation unit can extend an edge to an adjacent node in the vicinity of the start point. This Thus, the edge can be extended even when the position of the end point relative to the start point is unknown. It is also possible to extend the edge from the start point only in the direction near the end point.
  • the edge cost calculation node reading unit increases the cost of the edge extended from the target node to the adjacent node until the number of nodes from the start point to the adjacent node reaches the predetermined number.
  • the distance between a node and the adjacent node can be set, and when the predetermined number is not reached, the cost of the node can be greatly separated.
  • the route cost calculation unit determines the cost of the adjacent node until the number of nodes from the start point to the adjacent node reaches the predetermined number, which constitutes a route from the start point to the adjacent node. It can be calculated as the sum of the distances.
  • a cost evaluation device is a cost evaluation device used for route search for selecting a route having the lowest cost from a start point to an end point included in an area represented by a dalid. Is a node that extends an edge from the current node of interest, and a node that is a predetermined number of points along the route from the node of interest in the direction of the starting point is the reference node.
  • a distance preparation unit that calculates a first distance indicating a shortest distance from a reference node to the adjacent node and a second distance indicating a shortest distance from the reference node to the node of interest, or reads out from the database;
  • the cost of the wedge extending from the node of interest to the adjacent node is (the first distance minus the second distance).
  • an edge cost calculation unit that calculates the above.
  • a route search method is a route search method that selects a route from the start point to the end point included in an area represented by a grid and that has the lowest cost, and each grid is a node.
  • the cost of the edge extending from the current focused node to the adjacent node adjacent to this node is defined as a reference node that is a predetermined number of nodes back in the direction of the starting point along the route from the focused node.
  • a route search method is a route search method that selects a route from the start point to the end point included in an area represented by a grid and that has the lowest cost, and each grid is a node.
  • a first step of extending an edge to an adjacent node near the starting point and calculating a distance from the starting point to the adjacent node as a cost of the adjacent node; and a cost from the starting point to one node When the cost of one node is assumed, the node with the lowest cost of the node among the leading nodes located at the tip of the edge is set as the attention node, and adjacent to the attention node at least in front, diagonally right front, and diagonally left front
  • the second step includes a first distance indicating
  • the second distance indicating the shortest distance from the reference node to the target node is calculated, or the distance preparation process read from the database, and the cost of the edge extending from the target node to the adjacent node (the first distance equal to Edge cost calculation process calculated as (second distance) and a path cost from the starting point to the adjacent node as a sum of costs of edges constituting the path. Road cost calculation process.
  • the edge cost is calculated by (the first distance minus the second distance), the sum of the edge costs is used as the route cost, and the process is repeated while increasing the edge until the adjacent node reaches the end point. It is possible to accurately evaluate the cost in route search and improve the angle resolution of the route.
  • the moving body represents the moving means, the driving means for driving the moving means, and the surrounding environment as a grid, and the cost of the path from the start point to the end point included in the dalid space is low.
  • a route search means for selecting the smallest one, and a control means for controlling the drive means based on a route search result of the route search means, wherein the route search means uses each grid as a node and is currently focused on Next to the adjacent node
  • the cost of the edge extended to the node is defined as a reference node that is a predetermined number of nodes along the path from the target node in the direction of the start point.
  • a route cost calculation means for calculating a route cost from the start point to the end point, and a value calculated as one (second distance indicating the shortest distance from the reference node to the target node); And a route determination means for determining a route according to the cost.
  • the angular resolution of the path is improved by the more detailed cost evaluation based on the edge pattern, and the ideal shortest distance can be obtained. Since a route close to can be generated, a natural moving motion can be expressed by a moving object. The invention's effect
  • a route search device capable of generating an optimum route in a search space expressed by a dalid, a route search method, and a cost evaluation for generating an optimum route used in the route search device.
  • a mobile object equipped with a device and a route search device can be provided.
  • FIG. 1 is a perspective view showing a bipedal walking type robot according to an embodiment of the present invention.
  • FIG. 2 is a block diagram showing a robot according to an embodiment of the present invention.
  • FIG. 3 is a diagram showing details of a route search module according to the embodiment of the present invention.
  • FIG. 4 is a schematic diagram for explaining edges and costs used in the route determination process of the route determination device according to the exemplary embodiment of the present invention.
  • FIG. 5 is a schematic diagram for explaining an edge and its cost used in the route determination process of the route determination device according to the embodiment of the present invention.
  • FIG. 6A A diagram showing the shape of the wedge when tracing back two wedges.
  • FIG. 6B A diagram showing the shape of the wedge when tracing back two wedges.
  • FIG. 6C A diagram showing the shape of the wedge when tracing back two wedges.
  • FIG. 6D A diagram showing the shape of the wedge when tracing back two wedges.
  • FIG. 6E This is a diagram showing the shape of the wedge when going back two wedges.
  • FIG. 6F A diagram showing the shape of the wedge when tracing back two wedges.
  • FIG. 6G This is a diagram showing the shape of the wedge when going back two wedges.
  • FIG. 7 A is a diagram showing a route where node n 7 is the start point and node n 24 is the end point.
  • FIG. 7B is a diagram showing a route in which node n 7 is the start point and node n 24 is the end point.
  • FIG. 7C is a diagram showing a route in which node n 7 is the start point and node n 24 is the end point.
  • FIG. 7D is a diagram showing a route with node ⁇ 7 as the start point and node ⁇ 24 as the end point.
  • FIG. 7E is a diagram showing a route with node ⁇ 7 as the start point and node ⁇ 24 as the end point.
  • FIG. 7F is a diagram showing a route with node ⁇ 7 as the start point and node ⁇ 24 as the end point.
  • FIG. 8 is a diagram showing a moving path of a conventional robot.
  • FIG. 9 is a diagram showing a movement path of the robot according to the embodiment of the present invention.
  • FIG. 10 is a flowchart showing a route determination method according to an embodiment of the present invention.
  • FIG. 11 is a flowchart showing a method for calculating an edge cost in the route determination device according to the exemplary embodiment of the present invention.
  • FIG. 12A is a schematic diagram showing a route search process according to the embodiment of the present invention in order of process.
  • FIG. 12B is a schematic diagram showing the route search process according to the embodiment of the present invention in the order of processes.
  • FIG. 12C The route search process according to the embodiment of the present invention is performed in the order of processes. It is a schematic diagram shown in FIG.
  • FIG. 12D is a schematic diagram showing the route search process according to the embodiment of the present invention in order of process.
  • FIG. 12E is a schematic diagram showing the route search process according to the embodiment of the present invention in order of process.
  • FIG. 12F is a schematic diagram showing the route search process according to the embodiment of the present invention in the order of processes.
  • FIG. 12G is a schematic diagram showing the route search process according to the embodiment of the present invention in order of process.
  • FIG. 12H is a schematic diagram showing the route search process according to the embodiment of the present invention in the order of steps.
  • FIG. 12 I is a schematic diagram showing the route search process according to the embodiment of the present invention in order of process.
  • FIG. 13A is a schematic diagram showing a conventional route search process in the order of processes.
  • FIG. 13B is a schematic diagram showing a conventional route search process in the order of steps.
  • FIG. 13C is a schematic diagram showing a conventional route search process in the order of steps.
  • FIG. 13D is a schematic diagram showing a conventional route search process in the order of processes.
  • FIG. 13E is a schematic diagram showing a conventional route search process in the order of steps.
  • FIG. 13F is a schematic diagram showing a conventional route search process in the order of steps.
  • FIG. 13G is a schematic diagram showing a conventional route search process in the order of steps.
  • FIG. 13H is a schematic diagram showing a conventional route search process in the order of processes.
  • FIG. 13 I is a schematic diagram showing a conventional route search process in the order of steps.
  • FIG. 13 J is a schematic diagram showing a conventional route search process in the order of processes.
  • FIG. 13K is a schematic diagram showing a conventional route search process in the order of processes.
  • FIG. 14 shows the results of the route search method according to the embodiment of the present invention. It is a figure which shows the path
  • FIG. 15A is a schematic diagram showing the route search process according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle exists.
  • FIG. 15B is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle exists.
  • FIG. 15 C is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle is present.
  • FIG. 15D is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle exists.
  • FIG. 15 E is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle is present.
  • FIG. 15 F is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle exists.
  • FIG. 15 G is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle exists.
  • FIG. 15 H is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle exists.
  • FIG. 15 I is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle is present.
  • FIG. 15 J is a schematic diagram showing the route search step according to the embodiment of the present invention in the order of steps, and is a diagram showing the route search step when an obstacle exists.
  • the present invention is applied to a route searching apparatus mounted on a mouth pot or the like.
  • a grid route that is as close as possible to the ideal shortest distance is generated in the route search in the dull-like search space. And not only the length of the line segment, The cost of each edge (line segment) in the route is evaluated by considering the passing point of the route. First, a robot on which such a route search device is mounted will be described.
  • FIG. 1 is a perspective view showing a robot according to an embodiment of the present invention.
  • the robot 1 has a head unit 2 at a predetermined position on the trunk mute 5, two left and right arm mute 3a, 3b, and two left and right leg units 4a. 4 b are connected.
  • the robot 1 according to the present embodiment is configured to be movable by wheels built in the leg units 4a and 4b.
  • the robot may be a biped or quadruped walking type robot.
  • the head unit 2 includes an imaging unit 6 and can capture a predetermined range around the head unit 2.
  • the head mute 2 is provided with a microphone, a speaker, etc. (not shown), and can recognize and answer the call from the user.
  • the head unit 2 is connected to the trunk unit 5 so as to be turnable in the left-right direction in a plane horizontal to the floor surface, and images are obtained by turning the head unit 2.
  • the range can be changed according to the situation, and the surrounding environment can be imaged.
  • the arm unit 3a, 3b and the leg unit 4a, 4b are respectively processed by the arithmetic processing unit included in the control unit built in the trunk unit 5, according to a predetermined control program.
  • the amount of driving of the wheel included in the joint part and leg unit 4a, 4b included in 3b is controlled, and the joint driving angle of each joint and the rotation angle of the wheel are determined. It takes the position and posture.
  • FIG. 2 is a block diagram showing the robot according to the present embodiment.
  • the robot 1 includes a control unit 101, an input / output unit 102, a drive unit 103, a power supply unit 104, an external storage unit 105, and the like.
  • the input / output unit 102 has a camera 1 2 1 consisting of a CCD (Charge Coupled Device) for acquiring surrounding images, one or more built-in microphones 122 for collecting surrounding sounds, and audio. It includes a speaker power 123 for outputting and interacting with the user, an LED 124 for expressing responses and emotions to the user, and a sensor unit 125 including a touch sensor.
  • CCD Charge Coupled Device
  • the drive unit 103 includes a motor 1 3 1 and a dryer 1 32 that drives the motor, and the leg units 4 a and 4 b and the arm units 3 a and 3 b are attached according to user instructions. Make it work.
  • the power supply unit 104 includes a battery 141 and a battery control unit 142 that controls the discharging and charging thereof, and supplies power to each unit.
  • the external storage unit 105 includes a detachable HDD, optical disk, magneto-optical disk, etc., stores various programs and control parameters, and stores the programs and data as needed in the memory in the control unit 1001. (Not shown)
  • the control unit consists of CPU (Central Processing Unit), ROM (Read It has only memory (RAM), random access memory (RAM), and an interface for wireless communication, and controls various operations of the robot 1.
  • the control unit 101 performs a route search based on the image recognition module 12 that analyzes the video acquired by the camera 12 1 and the image recognition result, for example, according to the control program stored in the ROM. It has a route search module 1 3, an action decision module 14 that selects actions to be taken based on various recognition results, and a voice recognition module 15 that performs voice recognition.
  • the route search module 1 3 generates an ideally close search route, and controls the drive unit 10 3 based on this, so that the robot 1 performs a more natural movement operation. Express.
  • the robot 1 searches the route to be taken in the route search module 13 by approximating the moving space in a grid shape.
  • the route search module according to the present embodiment will be described in detail.
  • FIG. 3 is a diagram showing details of the route search module according to the present embodiment.
  • the route search module 13 has a route output unit 20 and a distance cost database (DB) 30.
  • the distance ′ cost DB 30 stores the cost calculated from each dalid to each dalid and the distance between each dalid calculated in advance.
  • each grid is a node, a node that extends an edge from the current node of interest is an adjacent node, and a node that is a predetermined number of points back from the node of interest along the route is used as a reference.
  • Node the first distance indicating the shortest distance from the reference node to the adjacent node, and the attention node from the reference node
  • a second distance indicating the shortest distance to the card is stored.
  • the cost of the edge extended from the target node to the adjacent node is set to the first distance from the reference node to the adjacent node (tip node located at the tip of the edge) and the reference node to the target node (edge root). And the second distance to the root node).
  • the reference node is a node that goes back a predetermined number of times from the node of interest, and calculates the cost of an edge based on the shortest distance between multiple nodes. O More detailed cost evaluation based on the pattern can be performed, and the angular resolution of the route can be improved, and a route closer to the ideal shortest distance can be generated.
  • the route output unit 20 includes an edge generation unit 21, an edge cost calculation / reading unit 22, a route cost calculation unit 2 3, and a route determination unit 24.
  • the distance and cost DB 30 storing the cost and distance is stored, and the route output unit 20 appropriately refers to this data to perform the route search.
  • the route output unit 20 may calculate the cost and distance as needed.
  • the distance 'cost D B 30 can be constructed by the edge cost calculation Z reading unit 22 and the path cost calculation unit 23 of the route output unit 20.
  • the environment is recognized as a search space represented by a grid.
  • the robot apparatus results in a search problem with each grid as a node, and a known algorithm such as the Dijkstra method, A * search, or DP matching.
  • the optimal route can be determined by the At this time, the distance and cost between nodes is calculated and registered in the distance 'cost DB 30.
  • the distance and cost between nodes in the environment may be input from the outside.
  • each process of edge generation, edge cost reading calculation, path cost calculation, and path determination is performed at a rate of once every several milliseconds to several seconds, and a path is generated for each timing. Obstacle information etc. shall be input as information from the image recognition module or sensor at each timing.
  • each block will be described in detail.
  • the edge generation unit 21 1 selects the node with the lowest node cost from among the leading nodes located at the tip of the edge. An edge extending to an adjacent node located at least in front of the target node, diagonally right front, and diagonally left front is generated. Here, forward is the direction in which the edge entering the node of interest faces.
  • 4 and 5 are schematic diagrams for explaining the edge and its cost.
  • the edge generation unit 21 generates edges in three directions from the target node, forward, diagonally right front, and diagonally left front.
  • Figures 4 and 5 show the 4 x 4 grid (nl to nl 6).
  • the forward node is node ⁇ 8
  • the diagonally right front node is node ⁇ 4
  • the diagonally left node Becomes node ⁇ 1 2
  • the edge generation unit 2 1 generates an edge extending from the node ⁇ 7 to these nodes ⁇ 4, ⁇ 8, and ⁇ 1 2. .
  • edges are generated for all adjacent nodes in the vicinity of the up, down, left, and right diagonal directions 8 instead of the three directions.
  • the nodes other than the start point generate edges only in the three directions of forward, diagonally right front, and diagonally left front. It is also possible to generate five edges including the right side and left side nodes in addition to forward, right front and left front, for example. If the edges are generated only in three directions as in this embodiment, the amount of calculation is small and the processing speeds up.
  • edges are generated from all the neighboring nodes in the vicinity of 8 from the start point. However, the direction from the start point to the end point is obtained, and a part of the adjoining direction close to this direction is obtained. You may try to generate an edge only on the node.
  • the edge generation unit 21 uses the node with the lowest cost of each node, which will be described later, as the node of interest, and generates an edge at three neighboring nodes therefrom.
  • the cost of each node indicates the cost from the starting point to the node.
  • the edge cost calculation node 2 2 calculates the first distance indicating the shortest distance from the reference node to the adjacent node and the second distance indicating the shortest distance from the reference node to the node of interest, or reads it from the data pace.
  • Distance The separation preparation unit 2 2 a and an edge cost calculation unit 2 2 b that calculates the cost of the edge extending from the node of interest to the adjacent node as (the first distance minus the second distance).
  • the edge cost may be calculated in advance for each pattern and stored in the distance / cost DB 30. In that case, the edge cost calculation unit 2 2 b is not necessary.
  • FIGS. 6A to 6C and 6E to 6G, and FIGS. 6D and 6H have the same cost as the conventional method.
  • FIGS. 6A to 6H there are eight types of route patterns representing the leading edge node (adjacent node) g3 of the edge extended from the target node g2.
  • the node that goes back a predetermined number along the route from the node of interest g 2 in the starting point direction is the reference node.
  • the node g 1 that goes back two nodes (edges) is the reference node. .
  • tip node g 3 costs from the distance from reference node g 1 to tip node g 3 and from the distance from reference node g 1 to target node g 2 Can be sought.
  • the description will be made assuming that two edges are traced back. However, three or more edges may be traced back, or only one edge may be traced back.
  • the calculation of the edge cost will be specifically described.
  • the edge generation unit 21 starts from the node n 7.
  • Edges E1, E2, and E2 are generated.
  • a method for obtaining the cost of the edge E 1 of n 7 ⁇ n 12 will be described.
  • the reference node is node ⁇ 5 that goes back two edges from node n 7.
  • the distance L 1 from the reference node ⁇ 5 to the node ⁇ 12 which is the edge tip is read from the distance / cost DB 30.
  • the distance L 1 is expressed by the shortest distance from the node ⁇ 5 to ⁇ 12. This is the first distance.
  • the distance between each node is assumed to be 1.
  • the distance L 2 from the reference node n 5 to the target node n 7 that is the root of the edge is read from the distance cost DB 30.
  • the distance L2 is expressed by the shortest distance from the node n5 ⁇ n7. This is the second distance. In this example, the distance L2 is "2".
  • node n 5 that goes back two edges from node of interest n 1 1 becomes the reference node
  • the route cost calculation unit 23 is generated by the edge generation unit 21 from the start point.
  • the cost to the tip node of the selected edge is calculated.
  • the cost of each edge is stored in the distance / cost DB 30, the cost of each edge can be read and added.
  • the cost of the node n 5 ⁇ n 6 and the cost of the node n 6 ⁇ n 7 differ depending on the reference node for the nodes n 5 and n 6.
  • FIG. 7A to FIG. 7F are diagrams showing a path in which the node n 7 is the start point and the node n 24 is the end point.
  • Figures 7A to 7E show the same cost in the conventional cost calculation method. Therefore, the route determination unit 24 sometimes selects a route that deviates from the ideal route as shown in FIGS. 7A to 7D.
  • the cost shown in FIG. 7E is calculated as the minimum cost.
  • the path from the node n 7 to the node n 24 is the shortest ideal path shown in FIG.
  • Figure 7 F shows that the cost of the edges that make up the path is not simply a distance, but is evaluated by the difference in the distance between the edge of the edge and the root node from the reference node.
  • the route shown in Figure 7E that is closest to the ideal shortest route can be selected.
  • the route search result according to the present embodiment and the resolution of the generated route will be described.
  • the edge can be extended from a node to 8 neighboring nodes.
  • the minimum angle between the edges is 45 °.
  • a range of 45 ° Contains four patterns. In other words, approximately 45Z4 11.3.
  • the resolution is 4 times that of the case of expressing with one edge. This makes it possible to generate a route as shown in FIG. 7E instead of FIG. 7A to FIG. 7D. This makes it possible to generate a route with a turning angle of the robot of less than 45 °, and the robot can move smoothly without turning suddenly.
  • FIGS. 8 and 9 are diagrams showing the movement paths of the robot according to the conventional and the present embodiment, respectively.
  • the conventional robot device can only take a path turning diagonally to the right or left at 45 ° or 90 °.
  • FIG. 9 when the edge can be traced back by two edges and the path can be expressed by three edges as shown in FIG. Between the two, namely 11. It is possible to turn around 3 ° and around 22.6, and it is possible to draw a smooth curved path and to express natural movement as a robotic device.
  • FIG. 10 is a flowchart showing a route determination method according to the embodiment
  • FIG. 11 is a flowchart showing an edge cost calculation method.
  • FIGS. 12A to 12 1 are diagrams illustrating a route search method according to the present embodiment
  • FIGS. 13A to 13K are diagrams illustrating a conventional route search method
  • FIG. 14 is a route search according to the present embodiment.
  • FIGS. 15A to 17J are diagrams showing routes generated by the method
  • FIG. 15A to FIG. 17J are route search methods according to the present embodiment when there is an obstacle.
  • the edge generation unit 21 confirms that the node of interest is the starting point, the edge generation unit 21 extends the edge to all the neighboring nodes in the vicinity of the left, right, up, and down diagonals (step S 1).
  • the cost is calculated by the same method as the conventional method as the cost of the two nodes from the starting point (step S2).
  • the edge generation unit 21 generates edges for all eight neighboring nodes adjacent to the start node n 7.
  • the left side is the boundary of the grid area, so the edge cannot be extended to the left side, top left, or bottom left.
  • This creates edges that extend from the start node n 7 to the nodes 11 1, 11 2, 11 8, 11 1 4, and n 13.
  • the cost of the edge from the starting point ⁇ 7 force is the cost of each node ⁇ 1, ⁇ 2, ⁇ 8, ⁇ 14, and ⁇ 13. That is, the edge cost calculation / reading unit 22 reads the distance from the start node ⁇ 7.
  • the edge generation unit 21 selects the node with the lowest cost among the leading nodes of each edge (step S3).
  • the costs from the starting point to n l, ⁇ 2, ⁇ 8, ⁇ 14, and ⁇ 13 are the distances, and are 1, 1.41, 1, 1.41, and 1, respectively.
  • the edge generation unit 21 selects the nodes ⁇ 8 and ⁇ 13 with the lowest cost. Note that ⁇ 1 is the outermost circumference of the grid, and the cost cannot be calculated any more, so it is not subject to calculation.
  • the edge generation unit 21 extends the edge from ⁇ 8 and ⁇ 13 to the three directions of the front, the diagonally forward right, and the diagonally left front, with the direction of the edge entering ⁇ 8 and ⁇ 13 as the front (Ste S 4).
  • the edge of the edge extended from ⁇ 8 and ⁇ 13 Since the number of nodes up to the node is 2, the process returns to step S 2 and can be obtained as the distance of the cost edge of the edge as described above.
  • the cost of the tip node of each edge is the distance from the starting point. For example, the edge extends from n 8 to the right diagonally forward node n 3, forward node n 9, left diagonally forward node n 15, and the cost of each tip node is found as 2. 41, 2, 2. 41 respectively ( Step S 3).
  • the node with the lowest node cost is 1.41 of n2, ⁇ 114 (step S3). Therefore, the edge is extended from the n 2 and n l 4 to the right diagonally forward, forward node, and diagonally left forward node (step S 4).
  • n 3 has an edge extending from n 8.
  • the route with the lower node cost shall be adopted.
  • the route with the same node cost shall adopt the route that has been extended first.
  • the cost of node n 3 in the route from node n 2 is 2.41, and the cost of node n 3 in the route from node n 8 is 2, so the route from node n 2 is Not adopted.
  • the edge extends from node n 14 to nodes n 15, n 21, and n 20, and the edges extending from node n 15 and n 20 are routed from node n 8 and route from node 13, respectively. n 14 Force and other routes are not adopted. Repeat the process from step S2 until the number of edge nodes with extended edges reaches 3.
  • the edge cost calculation Z reading unit 22 selects the one with the lowest cost of the edge node of each edge, in the state of FIG. 12B, the node n 9 N 19 is selected. Therefore, as shown in FIG. 12C, the edges are extended from the node n 9 and the node n 19 to the front and left and right diagonally forward nodes.
  • the cost of the edge is calculated. First, at the tip node n4, nl O, nl 6, n 25, n 26 where the edge is extended, whether the number of nodes from the start node n 7 is 3 or more. judge. Here, the number of nodes is 3, and the process proceeds to step S6.
  • step S 6 two edges are traced back from the current node of interest n 9 and n 1 9 to examine the edge pattern. Going back two nodes from node n 9 becomes node n 7 (starting node), which becomes the reference node.
  • the edge pattern is a pattern from the reference node n7 to the tip nodes n4, ⁇ 10, n16. Based on this edge pattern, the cost of the leading nodes n4, n10, n16 is calculated (step S7).
  • the cost of the leading nodes n4, n10, and n16 can be obtained by the path cost calculation unit 23 by the cost from the starting point to the reference node + the cost based on the edge pattern from the reference node to the leading node. it can.
  • the cost from the start point to the reference node can be calculated by reading the costs of the edges constituting the route from the start point to the reference node from the distance 'cost DB 30 force by the edge cost calculation Z reading unit 22 and adding them.
  • the cost of the tip node is obtained from the edge pattern from the reference node to the tip node, and the costs of the tip nodes n4, n10, and n16 are 3. 16, 3, 3.
  • the reference node of the node of interest n 9 is the starting node n 7.
  • the edge cost of the node n 9 ⁇ ⁇ 4 is obtained.
  • the edge cost calculation // reading unit 22 may calculate the cost of the edge in this way, or read the distances L l and L2 from the distance 'cost DB 30 and calculate L 1 and L 2. May be.
  • distance and cost are calculated for all nodes (steps S15 and S16).
  • the edge cost of n 9 ⁇ n 1 0 is ⁇ distance L 1 (2 3) from reference node n 7 to edge node n 1 0 of the edge ⁇ — ⁇ base node of edge from reference node n 7
  • the costs of the nodes n 4, n l O, and ⁇ 16 are 3.16, 3, and 3.16, respectively.
  • the cost of node ⁇ 26 is 3. 16 and the cost of ⁇ 25 is 3.
  • the cost of node ⁇ 27 shown in Fig. 12 is explained.
  • the node ⁇ 2 7 is generated from the node ⁇ 20 and the path from the node ⁇ 2 1 is entered, but the previously generated route from the node ⁇ 20 is generated later.
  • the cost of ⁇ 2 7 is obtained by extending the edge from ⁇ 20 to ⁇ 2 7
  • the route with the edge extending from node n 20 is generated earlier for node n 27, but the route via node n 21 is cheaper as the cost of node n 27.
  • the route from node ⁇ 20 is not adopted as the route, and the cost from node ⁇ 21 is adopted.
  • FIG. 14 is a diagram in which a route is generated from the start point ST by the route search method according to the present embodiment. If no end point is set, the route is generated as shown in Fig. 14.
  • Figures 15A through 15J show the route search results when there are obstacles.
  • Fig. 15 A to Fig. 15 J if there are obstacles 4 3 in the area containing nodes n 8, n 9, nl 4, nl 5, n 2 0, n 2 1, obstacle 4 3 Route generated from the top to the end point (n 7 ⁇ n 1 3 ⁇ n 1 9 ⁇ n 2 6 ⁇ n 2 7 ⁇ n 2 2) and the route generated from the bottom of the obstacle 4 3 to the end point (N 7 ⁇ n 2 ⁇ n 3 ⁇ n 1 0 ⁇ n 1 l ⁇ n 1 8) is generated, but the route generated from the bottom to the end direction first reaches the end point n 1 8
  • the cost of the edge extended from the target node to the adjacent node is not simply set as the distance, but the first distance from the reference node to the adjacent node (tip node) and the reference Obtained from the second distance from the node to the target node (root node).
  • the reference node is a node that goes back one or more times from the node of interest, and calculates the cost of the edge based on the shortest distance between multiple nodes. Therefore, the cost of the edge is compared to the uniform cost evaluation as the edge distance. More detailed cost evaluation based on the pattern can be performed, and the angular resolution of the route is improved, and the route can be generated closer to the ideal shortest distance. Furthermore, more detailed cost evaluation based on the edge pattern can improve the angular resolution of the route and generate a route closer to the ideal shortest distance. It can be made.
  • the present invention is not limited to the above-described embodiments, and various modifications can be made without departing from the scope of the present invention.
  • the hardware configuration has been described.
  • the present invention is not limited to this, and any processing can be realized by causing a CPU (Central Processing Unit) to execute a computer program.
  • the computer program can be provided by being recorded on a recording medium, or can be provided by being transmitted via the Internet or other transmission medium.
  • the present invention provides, for example, a route planning apparatus and a route planning method for selecting a route having the lowest cost from the start point to the end point included in the area represented by the grid, and the cost in the route plan apparatus. It can be widely used for a cost evaluation device for evaluating the above and a mobile object equipped with the route planning device.

Landscapes

  • Engineering & Computer Science (AREA)
  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Radar, Positioning & Navigation (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Strategic Management (AREA)
  • Economics (AREA)
  • Automation & Control Theory (AREA)
  • Remote Sensing (AREA)
  • Aviation & Aerospace Engineering (AREA)
  • Tourism & Hospitality (AREA)
  • Game Theory and Decision Science (AREA)
  • General Business, Economics & Management (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Theoretical Computer Science (AREA)
  • Quality & Reliability (AREA)
  • Development Economics (AREA)
  • Operations Research (AREA)
  • Marketing (AREA)
  • Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
  • Navigation (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Manipulator (AREA)

Abstract

　グリッドで表現される探索空間において最適な経路を生成する。経路探索装置は、各グリッドをノードとし、始点から任意のノードまでのコストを当該任意のノードのコストとしたとき、エッジの先端に位置する先端ノードのうち、ノードのコストが最小のノードを注目ノードとし、注目ノードの前方、左右斜め前に位置する隣接ノードまでエッジを延ばすエッジ生成部（２１）と、注目ノードから経路に沿って始点方向に所定数さかのぼったノードを基準ノードとしたとき、基準ノードから隣接ノードまでの最短距離（第１の距離）、及び基準ノードから注目ノードまでの最短距離（第２の距離）をデータベースから読み出すエッジコスト算出／読出部（２２）と、始点から隣接ノードまでの経路コストを、経路を構成するエッジのコストの和として算出する経路コスト算出部（２３）と、始点から終点までのコストが最小の経路を選択する経路決定部（２４）とを有する。

Description

明 細 書 経路計画装置及び方法、 コスト評価装置、 並びに移動体 技術分野
[ 0 0 0 1 ]
本発明は、 ダリッドで表された領域に含まれる始点から終点までの 経路のうち、 そのコストが最小のものを選択する経路計画装置及び経 路計画方法、 当該経路計画装置におけるコストを評価するためのコス ト評価装置、 並びに当該経路計画装置を搭載した移動体に関する。 背景技術
[ 0 0 0 2 ]
従来の経路探索装置としては、 特許文献 1に移動ロボットが出発点 から目的地に向かう経路を求める移動ロボット用経路計画システムが 開示されている。 この経路計画システムは、 環境内の物体の幾何マツ プを用いて、 位置姿勢を確率的に表した物体が占有する空間の分布を 表したグリッドマップを生成するダリッドマップ生成手段と、 生成し たグリッドマップから、 物体の位置姿勢の不確実性に応じた距離を用 いてポロノィグラフを生成するポロノィグラフ生成手段と、 生成した ポロノィグラフの上で、 物体との衝突可能性と経路長をコストとして
、 与えられた出発点から目的地へ向かう経路の探索を行う経路探索手 段とを備える。
[ 0 0 0 3 ]
この構成により、 物体の位置姿勢の不確実性に応じた距離を用いて ポロノィグラフを生成して、 生成した重み付きボロノィグラフの上で 、 コスト計算を行い経路の探索を行っているので、 従来のポロノィグ ラフよりも安全な経路を生成する。
[ 0 0 0 4 ]
このように、 従来の経路計画技術としては、 上記特許文献 1のよう に、 移動空間をグリッド状に近似し、 隣接するグリッド点を結ぶ経路 のコストを評価する技術が知られている。 このような経路探索システ ムでは、 探索された経路は、 隣接するグリッド点間を結ぶ線分の集合 として表現される。 このため、 経路のコストは各線分の和として評価 している。
[特許文献 1 ] 特開 2 0 0 5— 3 2 1 9 6号公報 発明の開示
発明が解決しょうとする課題
[ 0 0 0 5 ]
ここで、 コスト評価を線分の長さのみで行なうと、 最短経路探索を 行なった場合に最短経路が複数存在する場合がある。 図 7 Fは、 スタ ートからゴールまでの最短距離を示す図、 図 7 A乃至図 7 Eは、 グリ ッド点間を結んだ場合の最短距離を示す図である。 図 7 A乃至図 7 E に示す 5つの経路コストに差はない。 図 7 Fに示す理想的な経路は、 スタートとゴールを直線で結ぶ経路であるが、 図 7 A乃至図 7 Eの 5 つの経路のうち、 この理想的な経路に近いのは、 図 7 Eに示す経路で ある。 しかしながら、 従来の経路探索システムでは、 図 7 A乃至図 7 Dに示す経路が選ばれることがあり、 例えばロポットに当該経路探索 システムを搭載した場合には、 ロボットが不自然な移動を発現したり するという問題点がある。
[ 0 0 0 6 ]
すなわち、 グリッド格子状に離散ィ匕された探索空間では、 経路長が ダリッド点を結ぶ線分の単純な和として表現されるため、 任意の 2点 を結ぶ直線が最適であることを認識することができなかった。 よって 、 従来の経路探索システムでは、 図 7 A乃至図 7 Eの経路長が同一と して求まってしまうため、 図 7 Eに示す経路ではなく、 図 7 A乃至図 7 Dに示す経路が生成されることがあった。 このように、 従来の経路 探索システムにおいては、 経路の角度分解能が低く、 理想的な最短経 路に近い、 グリッド経路を探索することができないという問題点があ る。
[ 0 0 0 7 ]
本発明は、 このような問題点を解決するためになされたものであり 、 グリツドで表現される探索空間において最適な経路を生成すること ができる経路探索装置、 経路探索方法、 経路探索装置で使用される最 適な経路を生成するためのコスト評価装置、 及び経路探索装置を搭載 した移動体を提供することを目的とする。 課題を解決するための手段
[ 0 0 0 8 ]
本発明にかかる経路探索装置は、 グリッドで表された領域に含まれ る始点から終点までの経路のうち、 そのコストが最小のものを選択す る経路探索装置であって、 各グリッドをノードとし、 現在注目する注 目ノードからこれに隣接する隣接ノ一ドへ伸ばしたェッジのコストを 、 当該注目ノードから経路に沿って前記始点方向に所定数さかのぼつ たノードを基準ノードとし、
(当該基準ノードから前記隣接ノードまでの最短距離を示す第 1の距 離） 一 （前記基準ノードから前記注目ノードまでの最短距離を示す第
2の距離）
として求めた値とし、 前記始点から前記終点までの経路コストを算出 する経路コスト算出部と、 当該経路コストに応じて経路を決定する経 路決定部とを有するものである。
[ 0 0 0 9 ]
本発明においては、 注目ノードから隣接ノードへ伸ばしたエッジの コストを、 単純にその距離とするのではなく、 基準ノードから隣接ノ ード （エッジの先端に位置する先端ノード） までの第 1の距離と、 基 準ノードから注目ノード （エッジの根元に位置する根元ノード） まで の第 2の距離とから求める。 基準ノードは、 注目ノードから 1以上さ かのぼつたノードであり、 複数のノ一ド間の最短距離に基づきェッジ のコストを算出するため、 エッジの距離として一律にコスト評価する のに比べ、 そのエッジのパターンに基づいたより詳細なコスト評価を 行なうことができ、 経路の角度分解能が向上してより理想的な最短距 離に近い経路を生成することができる。
[ 0 0 1 0 ]
また、 前記経路コスト算出部は、 前記始点から前記終点までの経路 コストを当該経路を構成するエッジのコストの和として算出すること ができる。 単なる距離ではなく、 （第 1の距離一第 2の距離） として 求めたエッジのコストの総和を経路コストとすることができる。
[ 0 0 1 1 ]
さらに、 前記経路コスト算出部は、 前記第 1の距離及ぴ前記第 2の 距離、 又は （第 1の距離一第 2の距離） で求まるコストが格納された データベースを参照して前記始点から前記終点までのコストを算出す ることができる。 データベースを参照することで経路コスト算出を高 速化することができる。
[ 0 0 1 2 ]
さらにまた、 （前記第 1の距離一前記第 2の距離） を算出して前記 データベースを構築するデータベース生成部を更に有することができ
、 例えば経路探索を実行しつつデータベースを生成することができる [ 0 0 1 3 ]
また、 前記始点から任意のノードまでのコストを当該任意のノード のコストとしたとき、 エッジの先端に位置する先端ノードのうち、 ノ 一ドのコストが最小のノードを注目ノードとし、 注目ノードの少なく とも前方、 斜め右前、 及び斜め左前に位置する隣接ノードに伸ばすェ ッジを生成するエツジ生成部と、 前記第 1の距離及び前記第 2の距離 を算出又はデータベースから読み出すエッジコスト算出 Z読出部とを 有し、 前記経路コスト算出部は、 前記始点から前記隣接ノードまでの 経路コストを当該経路を構成するヱッジのコストの和として算出し、 前記経路決定部は、 前記隣接ノードが前記終点の場合、 前記始点から 前記終点までのコストが最小の経路を選択することができる。 注目ノ ードからエッジを生成し、 エッジのコストを求め、 経路を構成するェ ッジのコストの総和を経路コストとして求めることができる。
[ 0 0 1 4 ]
さらに、 前記エッジ生成部は、 前記注目ノードが前記始点の場合、 当該始点の 8近傍の隣接ノードにエッジを延ばすことができる。 この ことにより、 始点に対する終点の位置が不明な場合であってもエッジ を伸ばすことができる。 なお、 終点近傍の方向にのみ始点からエッジ を伸ばすことも可能である。
[ 0 0 1 5 ]
さらにまた、 前記エッジコス ト算出ノ読出部は、 前記始点から前記 隣接ノードまでのノード数が前記所定数になるまでは、 前記注目ノー ドから前記隣接ノ一ドまで伸ばしたェッジのコストを前記注目ノード と前記隣接ノードとの距離とすることができ、 所定数に達しない場合 は、 ノードのコストを足巨離とすることができる。
[ 0 0 1 6 ]
同様に、 前記経路コス ト算出部は、 前記始点から前記隣接ノードま でのノード数が前記所定数になるまでは、 前記隣接ノードのコストを 前記始点から前記隣接ノードまでの経路を構成するェッジの距離の和 として算出することができる。
[ 0 0 1 7 ]
本発明にかかるコスト評価装置は、 ダリッドで表された領域に含ま れる始点から終点までの経路のうち、 そのコストが最小のものを選択 する経路探索に使用するコスト評価装置であって、 各ダリッドをノー ドとし、 現在注目する注目ノードからエッジを伸ばすノードを隣接ノ ードとし、 前記注目ノードから経路に沿って前記始点方向に所定数さ かのぼつたノードを基準ノードとしたとき、 当該基準ノ一ドから前記 隣接ノードまでの最短距離を示す第 1の距離、 及び前記基準ノードか ら前記注目ノードまでの最短距離を示す第 2の距離を算出、 又はデー タベースから読み出す距離準備部と、 前記注目ノードから前記隣接ノ 一ドへ伸ばすェッジのコストを （前記第 1の距離一第 2の距離） とし て算出するエッジコスト算出部とを有するものである。
[ 0 0 1 8 ]
本発明にかかる経路探索方法は、 グリッドで表された領域に含まれ る始点から終点までの経路のうち、 そのコストが最小のものを選択す る経路探索方法であって、 各グリッドをノードとし、 現在注目する注 目ノードから、 これに隣接する隣接ノードへ伸ばすエッジのコストを 、 当該注目ノードから経路に沿って前記始点方向に所定数さかのぼつ たノードを基準ノードとし、
(当該基準ノードから前記隣接ノードまでの最短距離を示す第 1の距 離） 一 （前記基準ノードから前記注目ノードまでの最短距離を示す第
2の距離）
として求めた値として前記始点から前記終点までの経路コストを算出 する経路コスト算出工程と、 当該経路コストに応じて経路を決定する 経路決定工程とを有するものである。
[ 0 0 1 9 ]
本発明にかかる経路探索方法は、 グリッドで表された領域に含まれ る始点から終点までの経路のうち、 そのコストが最小のものを選択す る経路探索方法であって、 各グリッドをノードとし、 前記始点の 8近 傍の隣接ノードにエッジを延ばし、 当該始点から前記隣接ノードまで の距離を当該隣接ノードのコストとして算出する第 1工程と、 前記始 点から一のノードまでのコストを当該一のノードのコストとしたとき 、 エッジの先端に位置する先端ノードのうち、 ノードのコストが最小 のノードを注目ノードとし、 当該注目ノードの少なくとも前方、 斜め 右前、 及ぴ斜め左前に位置する隣接ノードまでエッジを延ばし、 当該 隣接ノードのコストを算出する第 2工程と、 当該隣接ノードが前記終 点の場合、 前記始点から前記終点までのコストが最小の経路を選択す る第 3工程とを有し、 前記隣接ノ一ドが前記終点となるまで前記第 2 工程を繰り返すものであって、 前記第 2工程は、 前記注目ノードから 経路に沿って始点方向に所定数さかのぼったノードを基準ノードとし たとき、 当該基準ノードから前記隣接ノードまでの最短距離を示す第 1の距離、 及ぴ前記基準ノードから前記注目ノードまでの最短距離を 示す第 2の距離を算出し、 又はデータベースから読み出す距離準備ェ 程と、 前記注目ノードから前記隣接ノードへ伸びるエッジのコストを (前記第 1の距離一第 2の距離） として算出するエッジコスト算出ェ 程と、 前記始点から前記隣接ノードまでの経路コストを当該経路を構 成するエッジのコストの和として算出する経路コスト算出工程とを有 するものである。
[ 0 0 2 0 ]
本発明においては、 （第 1の距離一第 2の距離） によりエッジコス トを算出し、 このエッジコストの和を経路コストとし、 隣接ノードが 終点となるまでェッジを増殖しながら処理を繰り返すことにより、 経 路探索におけるコストを正確に評価することができ、 経路の角度分解 能を向上させることができる。
[ 0 0 2 1 ]
本発明にかかる移動体は、 移動手段と、 前記移動手段を駆動する駆 動手段と、 周囲の環境をグリッドで表し、 当該ダリッド空間に含まれ る始点から終点までの経路のうち、 そのコストが最小のものを選択す る経路探索手段と、 前記経路探索手段の経路探索結果に基づき前記駆 動手段を制御する制御手段とを備え、 前記経路探索手段は、 各グリツ ドをノードとし、 現在注目する注目ノードからこれに隣接する隣接ノ ードへ伸ばしたエッジのコストを、 当該注目ノードから経路に沿って 前記始点方向に所定数さかのぼったノードを基準ノードとし、 （当該 基準ノードから前記隣接ノードまでの最短距離を示す第 1の距離） 一 (前記基準ノ一ドから前記注目ノードまでの最短距離を示す第 2の距 離） として求めた値とし、 前記始点から前記終点までの経路コストを 算出する経路コスト算出手段と、 当該経路コストに応じて経路を決定 する経路決定手段とを有するものである。
[ 0 0 2 2 ]
本発明においては、 経路探索手段がエッジの距離として一律にコス ト評価するのに比べ、 そのエッジのパターンに基づいたより詳細なコ スト評価により経路の角度分解能が向上してより理想的な最短距離に 近い経路を生成することができるので、 移動体により自然な移動動作 を表出させることができる。 発明の効果
[ 0 0 2 3 ]
本発明によれば、 ダリッドで表現される探索空間において最適な経 路を生成することができる経路探索装置、 経路探索方法、 経路探索装 置で使用される最適な経路を生成するためのコスト評価装置、 及ぴ経 路探索装置を搭載した移動体を提供することができる。 図面の簡単な説明
[ 0 0 2 4 ]
[図 1 ] 本発明の実施の形態にかかる 2足歩行タイプのロボット を示す斜視図である。 [図 2 ] 本発明の実施の形態にかかるロボットを示すプロック図 である。
[図 3 ] 本発明の実施の形態にかかる経路探索モジュールの詳細 を示す図である。
[図 4 ] 本発明の実施の形態にかかる経路決定装置の経路決定処 理にて使用するエッジ及ぴそのコストを説明するための模式図である o
[図 5 ] 同じく、 本発明の実施の形態にかかる経路決定装置の経 路決定処理にて使用するエツジ及びそのコストを説明するための模式 図である。
[図 6 A] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 6 B ] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 6 C] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 6 D] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 6 E] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 6 F ] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 6 G] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 6 H] 2つ分のェッジをさかのぼる場合のェッジの形状を示 す図である。
[図 7 A] ノード n 7が始点、 ノード n 24が終点の経路を示す 図である。
[図 7B] ノード n 7が始点、 ノード n 24が終点の経路を示す 図である。
[図 7C] ノード n 7が始点、 ノード n 24が終点の経路を示す 図である。
[図 7D] ノード η 7が始点、 ノード η 24が終点の経路を示す 図である。
[図 7E] ノード η 7が始点、 ノード η 24が終点の経路を示す 図である。
[図 7F] ノード η 7が始点、 ノード η 24が終点の経路を示す 図である。
[図 8] 従来のロボットの移動経路を示す図である。
[図 9] 本発明の実施の形態にかかるロボットの移動経路を示す 図である。
[図 10] 本発明の実施の形態にかかる経路決定方法を示すフロ 一チヤ一トである。
[図 11] 本発明の実施の形態にかかる経路決定装置におけるェ ッジのコスト算出方法を示すフローチヤ一トである。
[図 12A] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12B] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12 C] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12D] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12E] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12F] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12G] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12H] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 12 I] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図である。
[図 13A] 従来の経路探索工程を工程順に示す模式図である。
[図 13B] 従来の経路探索工程を工程順に示す模式図である。
[図 13C] 従来の経路探索工程を工程順に示す模式図である。
[図 13D] 従来の経路探索工程を工程順に示す模式図である。
[図 13E] 従来の経路探索工程を工程順に示す模式図である。
[図 13F] 従来の経路探索工程を工程順に示す模式図である。
[図 13G] 従来の経路探索工程を工程順に示す模式図である。
[図 13H] 従来の経路探索工程を工程順に示す模式図である。
[図 13 I] 従来の経路探索工程を工程順に示す模式図である。
[図 13 J] 従来の経路探索工程を工程順に示す模式図である。
[図 13K] 従来の経路探索工程を工程順に示す模式図である。
[図 14] 本発明の実施の形態にかかる経路探索方法によって生 成される経路を示す図である。
[図 1 5 A] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 B] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 C] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 D] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 E] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 F] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 G] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 H] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。 [図 1 5 I ] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。
[図 1 5 J ] 本発明の実施の形態にかかる経路探索工程を工程順 に示す模式図であって、 障害物が存在する場合の経路探索工程を示す 図である。 符号の説明
L 0 0 2 5 ]
1 πホッ卜
2 頭部ュニット
3 a、 3 b 腕部ュニット
4 a、 4 b 脚部ュニット
5 体幹部ュニット
6 撮像部
1 2 画像認識モジュール
1 3 経路探索モジュール
1 4 行動決定モジュール
1 5 音声認識モジュール
2 0 経路出力部
2 1 ェッジ生成部
2 2 エッジコスト算出ノ読出部
2 2 a 距離準備部
2 2 b エッジコスト算出部
2 3 経路コスト算出部 2 4 経路決定部
4 3 障害物
1 0 1 制御部
1 0 2 入出力部
1 0 3 駆動部
1 0 4 電源部
1 0 5 外部記憶部
1 2 1 カメラ
1 2 2 内蔵マイク
1 2 3 スピーカ
1 2 5 センサ部
1 3 1 モータ
1 3 2 ドライバ
1 4 1 パッテリ
1 4 2 パッテリ制御部 発明を実施するための最良の形態
[ 0 0 2 6 ]
以下、 本発明を適用した具体的な実施の形態について、 図面を参照 しながら詳細に説明する。 この実施の形態は、 本発明を、 口ポット等 に搭載する経路探索装置に適用したものである。
[ 0 0 2 7 ]
本実施の形態にかかる経路探索装置においては、 ダリッド状の探索 空間における経路探索において、 理想的な最短距離にできるだけ近い グリッド経路を生成する。 そして、 経路の線分の長さのみならず、 そ の経路の通過地点を考慮することにより、 経路中の各エッジ （線分） のコストを評価する。 ここでは先ず、 このような経路探索装置が搭载 されるロボットについて説明しておく。
[ 0 0 2 8 ]
図 1は、 本発明の実施の形態にかかるロボットを示す斜視図である
。 図 1に示すように、 ロボット 1は、 体幹部ュュット 5の所定の位置 に頭部ュニット 2、 左右 2つの腕部ュ-ット 3 a、 3 b、 及ぴ左右 2 つの脚部ユニット 4 a、 4 bが連結されている。 本実施の形態にかか るロボット 1は、 脚部ユニット 4 a、 4 bに内蔵された車輪により移 動可能に構成される。 なお、 ロボットは、 2足若しくは 4足歩行タイ プのロボットであってもよい。
[ 0 0 2 9 ]
頭部ュニット 2には、 撮像部 6が備えられ、 周囲所定範囲を撮影す ることが可能である。 また、 頭部ュュット 2には、 図示せぬマイク、 スピーカ等が備えられ、 ユーザからの呼びかけを認識したり、 それに 答えたりすることも可能である。 頭部ユニット 2は、 体幹部ユニット 5に対して床面に対して水平な面内で左右方向に回動可能に接続され ており、 頭部ュ-ット 2を回動することで撮像する範囲を状況に応じ て変更し、 周囲の環境を撮像することができる。
[ 0 0 3 0 ]
腕部ュニット 3 a、 3 b及び脚部ュニット 4 a、 4 bは、 体幹部ュ ニット 5に内蔵された制御部に含まれる演算処理部によって、 所定の 制御プログラムに従って各腕部ュニット 3 a、 3 bに含まれる関節部 、 脚部ュニット 4 a、 4 bに含まれる車輪の駆動する量が制御され、 各関節の関節駆動角度及び車輪の回転角度が決定されることで、 所望 の位置および姿勢をとるものである。
[003 1]
図 2は、 本実施の形態にかかるロボットを示すプロック図である。 ロボット 1は、 制御部 1 0 1、 入出力部 1 02、 駆動部 1 03、 電源 部 1 04、 及び外部記憶部 1 05などを有している。
[0032]
入出力部 1 02は、 周囲の映像を取得するための CCD (Charge Coupled Device) などからなるカメラ 1 2 1、 周囲の音を集音するた めの 1又は複数の内蔵マイク 1 22、 音声を出力してユーザと対話等 を行なうためのスピー力 1 23、 ユーザへの応答や感情等を表現する ための LED 1 24、 タツチセンサなどからなるセンサ部 1 25など を備 る。
[0033]
また、 駆動部 1 03は、 モータ 1 3 1及ぴモータを駆動するドライ ノ 1 32などを有し、 ユーザの指示などに従って脚部ユニット 4 a、 4 bや腕部ュニット 3 a、 3 bを動作させる。 電源部 1 04は、 バッ テリ 141及びその放充電を制御するパッテリ制御部 142を有し、 各部に電源を供給する。
[0034]
外部記憶部 1 05は、 着脱可能な HDD、 光ディスク、 光磁気ディ スク等からなり、 各種プログラムや制御パラメータなどを記憶し、 そ のプログラムやデータを必要に応じて制御部 1 0 1内のメモリ （不図 示） 等に供給する。
[003 5]
制御部は、 CPU (Central Processing Unit) 、 ROM (Read Only Memory) 、 R AM (Random Access Memory) 、 無線通信用のィ ンターフェースなどを有し、 ロボット 1の各種動作を制御する。 そし て、 この制御部 1 0 1は、 例えば R OMに格納された制御プログラム に従って、 カメラ 1 2 1により取得した映像を解析する画像認識モジ ユール 1 2、 画像認識結果に基づき、 経路探索を行なう経路探索モジ ユール 1 3、 各種認識結果に基づきとるべき行動を選択する行動決定 モジュール 1 4、 音声認識を行なう音声認識モジュール 1 5などを有 する。 特に、 本実施の形態においては、 経路探索モジュール 1 3によ り、 理想的に近い探索経路が生成され、 これに基づき駆動部 1 0 3を 制御するため、 ロボット 1はより自然な移動動作を表出する。
[ 0 0 3 6 ]
ここで、 本実施の形態にかかるロボット 1は、 経路探索モジュール 1 3において、 移動空間をグリッド状に近似し、 とるべき経路を探索 する。 次に、 本実施の形態にかかる経路探索モジュールについて詳細 に説明する。
[ 0 0 3 7 ]
図 3は、 本実施の形態にかかる経路探索モジュールの詳細を示す図 である。 経路探索モジュール 1 3は、 経路出力部 2 0及び距離' コス トデータベース （D B ) 3 0を有する。 距離' コスト D B 3 0には、 予め算出された各ダリッドから各ダリッドまでのコスト及ぴ各ダリッ ド間の距離が格納されている。 特に、 本実施の形態においては、 各グ リッドをノードとし、 現在注目する注目ノードからエッジを伸ばすノ 一ドを隣接ノードとし、 注目ノードから経路に沿って始点方向に所定 数さかのぼつたノードを基準ノードとしたとき、 基準ノードから隣接 ノードまでの最短距離を示す第 1の距離、 及び基準ノードから注目ノ ードまでの最短距離を示す第 2の距離が格納されている。 このことに より、 注目ノードから隣接ノードへ伸ばしたエッジのコストを、 基準 ノードから隣接ノード （エッジの先端に位置する先端ノード） までの 第 1の距離と、 基準ノードから注目ノード （エッジの根元に位置する 根元ノード） までの第 2の距離とから求めることができる。 基準ノー ドは、 注目ノードから所定数さかのぼったノードであり、 複数のノー ド間の最短距離に基づきエッジのコストを算出するため、 エッジの距 離として一律にコスト評価するのに比べ、 そのエッジのパターンに基 づいたより詳細なコスト評価を行なうことができ、 経路の角度分解能 が向上してより理想的な最短距離に近い経路を生成することができる o
[ 0 0 3 8 ]
経路出力部 2 0は、 エッジ生成部 2 1、 エッジコスト算出/読出部 2 2、 経路コスト算出部 2 3、 及び経路決定部 2 4を有する。 なお、 本実施の形態においては、 コスト及ぴ距離が格納された距離 · コスト D B 3 0を有し、 このデータを経路出力部 2 0が適宜参照して経路探 索を行なうものとして説明するが、 経路出力部 2 0において、 コスト 及ぴ距離を随時算出してもよい。 また、 距離'コスト D B 3 0は、 経 路出力部 2 0のエッジコスト算出 Z読出部 2 2及ぴ経路コスト算出部 2 3により構築することが可能である。
[ 0 0 3 9 ]
ここで、 本実施の形態においては、 新しい環境を認識する毎に、 当 該環境をグリッドで現された探索空間として認識するものとする。 そ して、 ロボット装置は、 各グリッドをノードとする探索の問題に帰着 し、 ダイキストラ法、 A *探索、 D Pマッチング等の公知のアルゴリ ズムにより、 最適経路を求めることができる。 その際、 ノード間の距 離及ぴコストを算出し、 距離'コスト D B 3 0に登録するものとする 。 なお、 口ポットにおいて新しい環境となる場合に当該環境における ノード間の距離 ·コストを外部から入力するようにしてもよい。 また 、 エッジ生成、 エッジコスト読出 算出、 経路コスト算出、 経路決定 の各処理は、 数 m秒乃至は数秒に 1回の割合で実施し、 当該タイミン グ毎に経路を生成するものとする。 なお、 当該タイミング毎に障害物 情報などは画像認識モジュールゃセンサからの情報として入力される ものとする。 以下、 各プロックについて詳細に説明する。
[ 0 0 4 0 ]
エッジ生成部 2 1は、 始点から一のノードまでのコストを当該一の ノードのコストとしたとき、 エッジの先端に位置する先端ノードのう ち、 ノードのコストが最小のノードを注目ノードとし、 注目ノードの 少なくとも前方、 斜め右前、 及び斜め左前に位置する隣接ノードに伸 ばすエッジを生成する。 ここで、 前方とは、 注目ノードに入るエッジ の向く方向である。 図 4及び図 5は、 エッジ及びそのコストを説明す るための模式図である。
[ 0 0 4 1 ]
エッジ生成部 2 1は、 注目するノードからその前方、 斜め右前、 斜 め左前の 3方向にエッジを生成する。 図 4、 図 5は、 4 X 4のグリツ ド （n l〜n l 6 ) を示している。 この図 4において、 注目するノー ドが η 7である場合、 ノード η 6からノード η 7に向く方向が前方で あり、 よって前方ノードはノード η 8、 斜め右前ノードはノード η 4 、 斜め左ノードはノード η 1 2となる。 エッジ生成部 2 1は、 ノード η 7からこれらノード η 4、 η 8、 η 1 2に伸びるエッジを生成する 。 ここで、 後述するように、 注目ノードが始点である場合には、 3方 向ではなく、 上下左右斜め方向 8近傍の隣接するノ一ド全てに対して エッジを生成するものとする。 なお、 本実施の形態においては、 始点 以外のノードにおいては、 前方、 斜め右前、 斜め左前の 3方向のみェ ッジを生成するものとして説明するが、 全ノードにおいて 8近傍の隣 接ノードに対してエッジを生成してもよく、 又は例えば前方、 右斜め 前、 左斜め前に加え、 右横及び左横ノードを含めた 5つのエッジを生 成するものとしてもよい。 本実施の形態のように、 3方向のみエッジ を生成することとすると計算量が少なく、 処理が高速化する。 また、 本実施の形態においては、 始点からは 8近傍の隣接ノード全てにエツ ジを生成するものとするが、 始点から終点に向く方向を求め、 この方 向に近い方向となる一部の隣接するノ一ドにのみェッジを生成するよ うにしてもよレ、。
[ 0 0 4 2 ]
ここで、 エッジ生成部 2 1は、 後述する各ノードのコストが最も小 さいノードを注目ノードとし、 そこから 3近傍ノードにエッジを生成 する。 本明細書において各ノードのコストとは、 始点から当該ノード までのコストを示すものとする。 エッジを生成したら、 さらに現在存 在するエッジの全ての先端ノードが有するノードのコストのうち、 最 小のノードのコストとなるノードを選択し、 同様にエッジを生成する 、 という処理を繰り返す。
[ 0 0 4 3 ]
エッジコスト算出ノ読出部 2 2は、 基準ノードから隣接ノードまで の最短距離を示す第 1の距離、 及び基準ノードから注目ノードまでの 最短距離を示す第 2の距離を算出、 又はデータペースから読み出す距 離準備部 2 2 aと、 注目ノードから隣接ノードへ伸ばすエッジのコス トを （前記第 1の距離一第 2の距離） として算出するエッジコスト算 出部 2 2 bとを有する。 なお、 エッジコストは、 各パターンについて 予め算出され、 距離 · コスト D B 3 0に格納されているものとしても よい。 その場合は、 エッジコスト算出部 2 2 bは不要である。
[ 0 0 4 4 ]
次に、 距離 ' コスト D B 3 0に格納されているエッジコストの算出 方法について説明する。 従来、 エッジのコストを評価する際には、 単 純にエッジの長さのみを使用していたのに対し、 本実施の形態におい ては、 注目しているノードに経路が到達するまでのエッジの形状から エッジのコストを評価 （算出） する。 エッジの形状のパターンは、 ェ ッジをどこまでさかのぼって評価するかによる。 評価に含める経路長 を長くする （エッジ数を多くする） ほど、 後述する経路の角度分解能 は向上する。 図 6 A乃至図 6 Hは、 2つ分のエッジをさかのぼる場合 のエッジの形状を示す図である。 この場合、 エッジの総数は 3である ので、 2 3 = 8通りのエッジのパターンを有することになる。 なお、 従来の方法で算出したコストと異なるのは、 図 6 A〜図 6 C及ぴ図 6 E〜図 6 Gであり、 図 6 D及ぴ図 6 Hは従来法と同一コストになる。 図 6 A乃至図 6 Hに示すように、 注目するノード g 2から伸ばしたェ ッジの先端ノード （隣接ノード） g 3を現す経路パターンが 8種類存 在する。 ここで、 当該注目するノード g 2から経路に沿って始点方向 に所定数さかのぼったノードを基準ノードとするが、 本例では、 2つ ノード （エッジ） をさかのぼったノード g 1を基準ノードとする。 注 目ノード g 2→先端ノード g 3のコストは、 基準ノード g 1から先端 ノード g 3の距離及ぴ基準ノード g 1から注目ノード g 2の距離から 求めることができる。 なお、 本実施の形態においては、 エッジを 2つ 分さかのぼることとして説明するが、 3つ以上さかのぼってもよく、 又は 1つのみさかのぼることとしてもよい。
[0045]
エッジコストの算出について具体的に説明する。 図 4に示すノード n 7を注目ノード、 ノード n l 2、 n 8、 n 4を、 ノード n 7力 ら延 ばしたエッジの先端ノードとするとき、 ノード n 7からは、 エッジ生 成部 21により、 エッジ E 1、 E2、 E2が生成される。 ここで n 7 →n 12のエッジ E 1のコストを求める方法について説明する。
[0046]
上述したように、 基準ノードはノード n 7から 2つ分のエッジをさ かのぼったノード η 5となる。 この基準ノード η 5からエッジの先端 であるノード η 12までの距離 L 1を距離 ·コスト DB 30から読み 出す。 距離 L 1は、 ノード η 5→η 12の最短距離で表される。 これ を第 1の距離とする。 なお、 本明細書においては、 各ノード間の距離 を 1として説明する。 本例では、 距離 L1は、 f (32+12) = ( 10) =3. 16となる。
[0047]
次に、 基準ノード n 5からエッジの根元である注目ノード n 7まで の距離 L 2を距離' コスト DB 30から読み出す。 距離 L2は、 ノー ド n 5→n 7の最短距離で表される。 これを第 2の距離とする。 本例 では、 距離 L2は、 "2"となる。 そして、 エッジ E 1のコスト =第 1 の距離 L 1一第 2の距離 L 2 = 3. 16— 2 = 1. 16として求める ことができる。
[0048] 他のエッジ E 2、 E 3についても同様に求めることができる。 すな わち、 エッジ E 2のコストは、 {基準ノード n 5からエッジ E 2の先 端ノード n 8までの距離 （第 1の距離） }一 {基準ノード n 5からエツ ジ E2の根元ノード n 7までの距離 （第 2の距離） } = 3— 2=1と なる。 また、 エッジ E3のコストは、 {基準ノード n 5からエッジ E 3の先端ノード n 4までの距離 （第 1の距離） }ー{基準ノード115か らエッジ E 3の根元ノード n 7までの距離 （第 2の距離） } = 3. 1 6— 2 = 1. 16となる。
[0049]
同様に、 図 5において、 注目ノード n 1 1からエッジを 2つさかの ぼったノード n 5が基準ノードとなり、 注目ノード n 1 1からノード n 12に伸ばしたエッジ E4のコストは、 {基準ノード n 5からエツ ジ E4の先端ノード n 12までの距離 （第 1の距離） }— {基準ノード n 5からエッジ E2の根元ノード n 1 1までの距離 （第 2の距離） } =3. 16-2. 24 = 0. 89となる。
[0050]
また、 エッジ E5のコストは、 {基準ノード n 5からエッジ E5の 先端ノード n 16までのコスト （第 1の距離） }ー{基準ノード n 5か らエッジ E5の根元ノード η 1 1までの距離 （第 2の距離） }=3. 61 -2. 24 = 1. 37となる。 さらに、 エッジ Ε 6のコストは、 {基準ノード η 5からエッジ Ε 6の先端ノード η 8までの距離 （第 1 の距離） }— {基準ノード η 5からエッジ Ε6の根元ノード η 1 1まで の距離 （第 2の距離） }= 3— 2. 24 = 0. 76となる。
[0051]
経路コスト算出部 23は、 始点から、 エッジ生成部 21にて生成さ れたエッジの先端ノードまでのコストを算出する。 この場合、 各エツ ジのコストは距離 ·コスト DB 30に格納されているため、 各エッジ のコストを読出し、 加算すればよい。 例えば、 図 4に示す例では、 始 点からノード n 12のコストは、 （始点から基準ノード n 5までのコ ス ト） + (n 5→n 6のコスト） + (n 6→n 7のコスト） + (エツ ジ E 1のコスト =1. 16) で現される。 ここで、 ノード n 5→n 6 のコストや、 ノード n 6→n 7のコストは、 当該ノード n 5、 n 6に 対する基準ノードによって異なってくる。 すなわち、 従来法のように 、 単純にこれらのコスト二距離 =1とならない場合がある。 同様に、 図 5に示す例では、 始点からノード n 12までのコストは、 （始点か ら基準ノード n 5までのコスト） + (n 5→n 6のコスト） + (n 6 →n l lのコスト） + (n 1 l→n 12のコスト =0. 89) となる
[0052]
経路決定部 24は、 ェッジ生成部 21が生成したェッジの先端ノ一 ドが終点になった場合、 当該始点から終点までのコストが最小のもの を経路として選択する。 図 7 A乃至図 7 Fは、 ノード n 7が始点、 ノ ード n 24が終点の経路を示す図である。 図 7 A乃至図 7 Eには、 従 来のコスト算出方法では同一コストとなる。 よって、 経路決定部 24 において、 図 7 A乃至図 7 Dに示すような理想的な経路から外れた経 路が選択される場合があった。 これに対し、 本実施の形態にかかる経 路コスト算出部 23の経路算出結果としては、 図 7Eに示すものがコ スト最小と算出される。 ここで、 ノード n 7からノード n 24までの 経路は、 ノードを無視すると単純にこれらのノードを直線で結んだ図 7 Fに示すものが最短の理想的な経路となる。 本実施の形態において は、 経路を構成するエッジのコストを単なる距離とするのではなく、 基準ノードにさかのぼり、 その基準ノードからのエツジの先端及び根 元ノードの距離の差により評価することで、 図 7 Fに示す理想的な最 短経路に最も近い図 7 Eに示す経路を選択することができる。
[0053]
次に、 本実施の形態にかかる経路探索結果、 生成される経路の分解 能について説明する。 ノード間を結ぶエッジのみで経路を表現する場 合、 あるノードから隣接する 8近傍のノ一ドにェッジを延ばすことが できる。 このとき、 エッジとエッジとの間の角度は最小で 45° とな る。 これに対し、 本実施の形態のように、 2つ分のエッジをさかのぼ り、 3つのエッジで表現するとした場合、 図 6H、 図 6B、 図 6C、 図 6Dに示すように、 45° の範囲内に 4つのパターンを含む。 すな わち、 約 45Z4 11. 3。 の分解能となり、 1本のエッジで表現 する場合に比して 4倍の分解能とすることができる。 これにより、 図 7A乃至図 7Dではなく、 図 7 Eのような経路を生成することを可能 としている。 このことにより、 ロボットの旋回角度が 45° 未満の経 路を生成することができ、 ロボットが急旋回することなく、 なめらか な動作をすることができる。
[0054]
図 8、 図 9はそれぞれ従来及び本実施の形態にかかるロボットの移 動経路を示す図である。 図 8に示すように、 従来のロボット装置は、 斜め右若しくは左に 45° 、 又は 90° に旋回する経路しかとること ができない。 これに対し、 本実施の形態のように、 2つ分エッジをさ かのぼり、 3つのエッジで経路を表現することができることとすると 、 図 9に示すように、 0乃至45。 の間に、 2つ、 すなわち、 11. 3° 付近と、 22. 6付近にも旋回することができるようになり、 な めらかな曲線の経路を描くことができ、 ロボット装置として自然な移 動動作を表出させることができる。
[0055]
次に、 本実施の形態にかかる経路探索方法について、 図 10及び図 1 1に示すフローチャート、 並びに図 12乃至図 15に示す経路図を 参照して具体的に説明する。 図 10は、 実施の形態にかかる経路決定 方法を示すフローチャート、 図 1 1は、 エッジのコスト算出方法を示 すフローチャートである。 図 12 A乃至図 12 1は、 本実施の形態に かかる経路探索方法を示す図、 図 13 A乃至図 13Kは、 従来の経路 探索方法を示す図、 図 14は本実施の形態にかかる経路探索方法によ つて生成される経路を示す図、 図 15 A乃至図 17 Jは、 障害物があ る場合の本実施の形態にかかる経路探索方法である。
[0056]
図 10に示すように、 先ず、 エッジ生成部 21は、 注目するノード が始点であることを確認すると、 左右上下斜めの隣接 8近傍のノード 全てにエッジを伸ばす （ステップ S 1) 。 そして、 この段階では、 始 点からの距離二ノードのコストとして従来と同様の方法にてコストを 算出する （ステップ S 2) 。
[0057]
具体的には、 図 12Aに示すように、 エッジ生成部 21は、 始点ノ ード n 7の隣接 8近傍ノード全てに対してエッジを生成する。 なお、 本例においては、 左側がグリッド領域の境界のため、 左横、 左上、 左 下へエッジを伸ばすことはできない。 これにより、 始点ノード n 7か らノード11 1、 11 2、 11 8、 11 1 4、 n 13に伸びるエッジが生成さ れる。 そして、 エッジコスト算出 Z読出部 22が注目ノードである始 点 n 7から次のノード n 1、 n 2、 n 8、 η 14、 η 13へ伸ばした エッジのコスト =距離として、 コストを求める。 ここでは、 始点 η 7 力 らのエッジのコストが各ノード η 1、 η2、 η 8、 η 14、 η 13 のコストとなる。 すなわち、 エッジコスト算出 Ζ読出部 22は、 始点 ノード η 7からの距離を読み出す。
[0058]
次に、 エッジ生成部 21は、 各エッジの先端ノードにおいて、 コス トが最小のノードを選択する （ステップ S 3) 。 図 12 Βにおいて、 始点から n l、 η 2、 η 8、 η 14、 η 13までのコストは、 その距 離であるから、 それぞれ 1、 1. 41、 1、 1. 41、 1となる。 こ のうちエッジ生成部 21は、 最小コストのノード η8、 η 13を選択 する。 なお、 η 1はグリッドの最外周であり、 これ以上コストは算出 できないので、 計算対象外となる。
[0059]
次に、 エッジ生成部 21は、 η 8、 η 13から、 η 8、 η 13に入 るエッジの方向を前方とし、 前方、 右斜め前、 左斜め前の 3方向にェ ッジを伸ばす （ステップ S 4) 。 次に、 エッジコスト算出 Ζ読出部 2 2は、 エッジのコストを求める前に、 始点から当該エッジの先端ノー ドまでのノード数 Ν≥ 3であるか否かを判定する。 本実施の形態にお いては、 注目するノードから 2つエッジをさかのぼってコストを評価 することとしているため、 始点から先端ノードまでの数 Ν= 3以上に なるまでは、 従来法と同様のコスト算出方法とする。
[0060]
図 12 Βに示すように、 η 8、 η 13から伸ばしたエッジの先端ノ ードまでのノード数は 2であるので、 ステップ S 2に戻り、 上述と同 様、 当該エッジのコストニエッジの距離として求めることができる。 そして、 各エッジの先端ノードのコストは、 それぞれ始点からの距離 となる。 例えば n 8からは右斜め前ノード n 3、 前方ノード n 9、 左 斜め前ノード n 15までエッジが伸ぴ、 各先端ノードのコストはそれ ぞれ 2. 41、 2、 2. 41と求まる （ステップ S 3) 。
[006 1]
次にノードのコストが最小のノードは、 n 2、 ∑114の1. 41で ある （ステップ S 3) 。 よって、 この n 2、 n l 4から、 右斜め前、 前方ノード、 左斜め前のノードにエッジを伸ばす （ステップ S 4) 。 ここで、 n 2から右斜め前方ノードは存在せず、 左斜め前ノードは n 3となる。 この場合、 n 3は n 8からのエッジが伸びている。 このよ うな場合は、 ノードのコストが低い方の経路を採用するものとする。 ノードのコストが同一の経路は、 先に伸びた経路を採用するものとす る。 本例においては、 ノード n 2からの経路におけるノード n 3のコ ストは 2. 41であり、 ノード n 8からの経路におけるノード n 3の コストは 2であるから、 ノード n 2からの経路は採用されない。 同様 にノード n 14からノード n 15、 n 21、 n 20にエッジが伸びる 力 ノード n 15、 n 20へ伸びるエッジはそれぞれノード n 8から の経路、 ノード 13からの経路が採用されるため、 ノード n 14力 ら の経路はいずれも採用されない。 エッジの伸ばした先端ノードまでの 数が 3になるまでステツプ S 2からの処理を繰り返す。
[0062]
次に、 エッジコスト算出 Z読出部 22は、 各エッジの先端ノードの コストが最小のものを選択すると、 図 12Bの状態では、 ノード n 9 、 n 19が選択される。 そこで、 図 12Cに示すように、 ノード n 9 、 ノード n 1 9から前方及ぴ左右斜め前ノードにエッジを伸ばす。 次 にエッジのコストを算出するが、 先ず、 エッジの伸びた先の先端ノー ド n4、 n l O、 n l 6、 n 25、 n 26において、 始点ノード n 7 からのノード数が 3以上であるか判定する。 ここでは、 ノード数が 3 となり、 ステップ S 6に進む。
[0063]
ステップ S 6では、 現在の注目ノード n 9、 n 1 9からエッジを 2 つさかのぼって、 そのエッジパターンを調べる。 ノード n 9からエツ ジを 2つさかのぼるとノード n 7 (始点ノード） になり、 これが基準 ノードとなる。 エッジパターンは、 基準ノード n 7から、 先端ノード n4、 η 10、 n 16までのパターンである。 このエッジパターンに 基づき、 先端ノード n4、 n 10、 n 16のコストを算出する （ステ ップ S 7) 。
[0064]
ここで、 先端ノード n4、 n 10、 n 16のコストは、 経路コスト 算出部 23により、 始点から基準ノードまでのコスト +基準ノードか ら先端ノードまでのエッジパターンに基づくコス トによって求めるこ とができる。 始点から基準ノードまでのコストは、 始点から基準ノー ドまでの経路を構成するエッジの各コストをエッジコスト算出 Z読出 部 22により距離 'コスト DB 30力 ら読出し、 加算すればよい。 本 例においては、 基準ノード =始点であるため、 基準ノードから先端ノ ードまでのエッジパターンにより、 当該先端ノードのコストが求まり 、 先端ノード n4、 n 10、 n 16のコストは、 それぞれ 3. 16、 3、 3. 16と求まる。 同様に、 先端ノード n 25、 n 26のコス ト は 3、 3. 16と求まる。 これらの処理を先端ノードが終点ノード n 24となるまで繰り替えし （ステップ S 8) 、 図 12D、 図 12E、 図 12F、 図 12Gを経て、 図 12Hの状態となる。 このとき、 ノー ド n l 7から伸ばしたエッジが終点ノード n 24に達するため、 先端 ノード =終点ノード n 24となる。 この時点で最小コストの経路を選 択して出力する （ステップ S 9) 。 本例においては、 図 121に示す ような経路が生成される。 この経路は、 図 7 Fに示す経路に最も近い 経路となっている。
[0065]
次に、 始点からエッジの先端ノードまでのコスト （先端ノードのコ ス ト） を算出する場合の方法について図 11を参照して説明する。 上 述したように注目ノード n 9の基準ノ一ドは始点であるノード n 7で ある。 先ず、 ノード n 9→η 4のエッジのコストを求める。 この場合 、 先ず、 図 11に示すように、 基準ノード η 7からエッジの先端ノー ド η4までの距離 L 1 (=3. 16) を算出する （ステップ S 11) 。 次に、 基準ノード η 7からエッジの根元ノード η 9までの距離 L 2 (=2) を算出する （ステップ S 12) 。 エッジのコストは、 L 1— L2 = l. 16と求めることができる （ステップ S 13) 。 このとき 、 距離 L 1、 L 2、 エッジのコストを距離 ·コスト DB 30に登録す ることで、 データベースを構築することができる。 なお、 エッジコス ト算出 //読出部 22は、 このようにエッジのコストを算出してもよい し、 距離 L l、 L2を距離'コス ト DB 30から読出し、 L 1一 L2 を算出するようにしてもよい。 データベースを構築する場合は、 全ノ ードについて、 距離及ぴコストを計算する （ステップ S 15、 S 16 ) 。 [0 06 6]
同様に、 n 9→n 1 0のエッジコス トは、 {基準ノード n 7からェ ッジの先端ノード n 1 0までの距離 L 1 (二 3) }— {基準ノード n 7 からエッジの根元ノード n 9までの距離 L 2 (= 2) }となり、 1と 求めることができる。 また、 n 9→n 1 6のエッジコス トは、 {基準 ノード n 7からエッジの先端ノード n 1 6までの距離 L 1 (= 3. 1 6) }ー{基準ノード n 7からエッジの根元ノード n 9までの距離 L 2 (= 2) }となり、 1. 1 6と求めることができる。 以上により、 各 ノード n 4、 n l O、 η 1 6のコストは、 それぞれ 3. 1 6、 3、 3 . 1 6となる。 同様に、 ノード η 26のコストは 3. 1 6、 η 2 5の コストは 3となる。
[00 6 7]
次に、 図 1 2 Εに示すノード η 27のコストについて説明する。 ノ ード η 2 7には、 ノード η 20からと、 ノード η 2 1からのエッジが 入る経路が生成されるが、 先に生成されるノード η 20からの経路の 方が、 後で生成されるノード η 2 1からの経路よりコストが大きく、 後で生成されるノード η 2 1からの経路が採用される例である。
[0 06 8]
先ず、 η 20から η 2 7へエッジを伸ばして η 2 7のコストを求め る場合について説明する。 ノード η 2 0→η 2 7のエッジのコス トは 、 （基準ノード η 7からノード η 2 7までの距離） 一 （基準ノード η 7からノード η 20までの距離） で求まり、 3. 6 1 - 2. 24 = 1 . 3 7となる。 この場合、 η 2 7のコス トは、 （η 7→η 1 3のコス ト） + (η 1 3→η 20のコスト） + ( η 20→ η 2 7のコスト） と なり、 1 + 1. 4 1 + 1. 3 7 = 3. 7 8となる。 [0069]
その後、 ノード ii 21から n 27へエッジを伸ばす経路が生成され る。 この場合、 n 2 l→n 27のエッジのコストは、 （基準ノード n 7から n 27までの距離） 一 （基準ノード η 7から η 21までの距離 ) で求まり、 3. 61 -2. 82 = 0. 79となる。 この場合、 η 2 7のコストは、 （η 7→η 14のコスト） + (n l 4→n 21のコス ト） + (n 2 l→n 27のコスト） となり、 1. 41 + 1. 41 + 0 . 79 = 3. 61となる。 このように、 ノード n 27についてノード n 20から伸びるエッジによる経路の方が早く生成されるが、 ノード n 27のコストとして n 21を経由する経路の方が安いため、 ここで はノード η 27の経路としてノード η 20からの経路は不採用となり 、 ノード η 21からのコストが採用となる。
[0070]
これに対し、 図 1 3 Α乃至図 1 3 Kに示すように、 従来法により経 路探索すると、 図 13Kに示すようなコストが抽出されてしまう。 そ の理由は、 この経路が従来法においては、 破線で示す理想の経路と同 様のコストになってしまうからである。 本実施の形態においては、 基 準ノードからエッジの先端及び根元ノードまでの距離に基づき、 当該 エッジのノードを算出するため、 理想的な経路に最も近い経路が生成 される。
[0071]
図 14は、 始点 STから本実施の形態にかかる経路探索方法にて経 路を生成した図である。 特に終点を設定しない場合は、 図 14に示す ように経路が生成されていく。
[0072] 図 1 5 A乃至図 1 5 Jは、 障害物がある場合の経路探索結果を示す 。 図 1 5 A乃至図 1 5 Jに示すように、 ノード n 8、 n 9、 n l 4、 n l 5、 n 2 0、 n 2 1を含む領域に障害物 4 3がある場合、 障害物 4 3の上から終点方向に生成される経路 （n 7→n 1 3→n 1 9→n 2 6→n 2 7→n 2 2 ) と、 障害物 4 3の下から終点方向に生成され る経路 （n 7→n 2→n 3→n 1 0→n 1 l→n 1 8 ) とが生成され るが、 下から終点方向に生成される経路が先に終点 n 1 8に到達する
[ 0 0 7 3 ]
本実施の形態においては、 注目ノードから隣接ノードへ伸ばしたェ ッジのコストを、 単純にその距離とするのではなく、 基準ノードから 隣接ノード （先端ノード） までの第 1の距離と、 基準ノードから注目 ノード （根元ノード） までの第 2の距離とから求める。 基準ノードは 、 注目ノードから 1以上さかのぼったノードであり、 複数のノード間 の最短距離に基づきエッジのコストを算出するため、 エッジの距離と して一律にコスト評価するのに比べ、 そのエッジのパターンに基づい たより詳細なコスト評価を行なうことができ、 経路の角度分解能が向 上してより理想的な最短距離に近レ、経路を生成することができる。 そ して、 そのエッジのパターンに基づいたより詳細なコスト評価により 経路の角度分解能が向上してより理想的な最短距離に近い経路を生成 することができるので、 ロボットにより自然な移動動作を表出させる ことができる。
[ 0 0 7 4 ]
なお、 本発明は上述した実施の形態のみに限定されるものではなく 、 本発明の要旨を逸脱しない範囲において種々の変更が可能であるこ とは勿論である。 例えば、 上述の実施の形態では、 ハードウェアの構 成として説明したが、 これに限定されるものではなく、 任意の処理を 、 C P U (Central Processing Unit) にコンピュータプログラムを 実行させることにより実現することも可能である。 この場合、 コンビ ユータプログラムは、 記録媒体に記録して提供することも可能であり 、 また、 インターネットその他の伝送媒体を介して伝送することによ り提供することも可能である。 産業上の利用可能性
[ 0 0 7 5 ] '
本発明は、 例えば、 グリッドで表された領域に含まれる始点から終 点までの経路のうち、 そのコストが最小のものを選択する経路計画装 置及ぴ経路計画方法、 当該経路計画装置におけるコストを評価するた めのコスト評価装置、 並びに当該経路計画装置を搭載した移動体に対 して広く利用できる。

Claims

1. グリッドで表された領域に含まれる始点から終点までの経路のう ち、 そのコストが最小のものを選択する経路探索装置であって、 各グリッドをノードとし、 現在注目する注目ノードからこれに隣接 卩
する隣接ノードへ伸ばしたエッジのコストを、 当該注目ノードから経 路に沿って前記始点方向に所定数さかのぼったノードを基準ノードと
3 6
し、
(当該基準ノードから前記隣接ノードまでの最短距離を示す第 1の距 囲
離） 一 （前記基準ノードから前記注目ノードまでの最短距離を示す第 2の距離）
として求めた値とし、 前記始点から前記終点までの経路コストを算出 する経路コスト算出部と、
当該経路コス トに応じて経路を決定する経路決定部とを有する経路 探索装置。
2. 前記経路コス ト算出部は、 前記始点から前記終点までの経路コス トを当該経路を構成するエッジのコストの和として算出する
ことを特徴とする請求項 1記載の経路探索装置。
3. 前記経路コスト算出部は、 前記第 1の距離及び前記第 2の距離、 又は （第 1の距離一第 2の距離） で求まるコストが格納されたデータ ベースを参照して前記始点から前記終点までのコストを算出する
ことを特徴とする請求項 1記載の経路探索装置。
4. (前記第 1の距離一前記第 2の距離） を算出して前記データべ一 スを構築するデータベース生成部を更に有する
ことを特徴とする請求項 3記載の経路探索装置。
5. 前記始点から任意のノードまでのコストを当該任意のノードのコ ストとしたとき、 エッジの先端に位置する先端ノードのうち、 ノード のコストが最小のノードを注目ノードとし、 注目ノードの少なくとも 前方、 斜め右前、 及び斜め左前に位置する隣接ノードに伸ばすエッジ を生成するエッジ生成部と、
前記第 1の距離及び前記第 2の距離を算出又はデータベースから読 み出すエッジコスト算出/ /読出部とを有し、
前記経路コスト算出部は、 前記始点から前記隣接ノードまでの経路 コストを当該経路を構成するエッジのコストの和として算出し、 前記経路決定部は、 前記隣接ノードが前記終点の場合、 前記始点か ら前記終点までのコストが最小の経路を選択する
ことを特徴とする請求項 1又は 2記載の経路探索装置。
6. 前記エッジ生成部は、 前記注目ノードが前記始点の場合、 当該始 点の 8近傍の隣接ノ一ドにェッジを延ばす
ことを特徴とする請求項 5記載の経路探索装置。
7. 前記エッジコスト算出/ /読出部は、 前記始点から前記隣接ノード までのノード数が前記所定数になるまでは、 前記注目ノードから前記 隣接ノ一ドまで伸ばしたェッジのコストを前記注目ノードと前記隣接 ノードとの距離とする
ことを特徴とする請求項 5又は 6記載の経路探索装置。
8. 前記経路コスト算出部は、 前記始点から前記隣接ノードまでのノ ード数が前記所定数になるまでは、 前記隣接ノードのコストを前記始 点から前記隣接ノードまでの経路を構成するエッジの距離の和として 算出する
ことを特徴とする請求項 5乃至 7のいずれか 1項記載の経路探索装 置。
9. グリッドで表された領域に含まれる始点から終点までの経路のう ち、 そのコストが最小のものを選択する経路探索に使用するコスト評 価装置であって、
各グリッドをノードとし、 現在注目する注目ノードからエッジを伸 ばすノードを隣接ノードとし、 前記注目ノードから経路に沿って前記 始点方向に所定数さかのぼったノードを基準ノードとしたとき、 当該 基準ノードから前記隣接ノードまでの最短距離を示す第 1の距離、 及 ぴ前記基準ノ一ドから前記注目ノードまでの最短距離を示す第 2の距 離を算出、 又はデータベースから読み出す距離準備部と、
前記注目ノードから前記隣接ノードへ伸ばすエッジのコストを （前 記第 1の距離一第 2の距離） として算出するエッジコスト算出部とを 有するコスト評価装置。
10. ダリッドで表された領域に含まれる始点から終点までの経路の うち、 そのコストが最小のものを選択する経路探索方法であって、 各グリッドをノードとし、 現在注目する注目ノードから、 これに隣 接する隣接ノードへ伸ばすエッジのコストを、 当該注目ノードから経 路に沿って前記始点方向に所定数さかのぼったノードを基準ノードと し、
(当該基準ノードから前記隣接ノードまでの最短距離を示す第 1の距 離） 一 （前記基準ノードから前記注目ノードまでの最短距離を示す第 2の距離）
として求めた値として前記始点から前記終点までの経路コストを算出 する経路コスト算出工程と、
当該経路コストに応じて経路を決定する経路決定工程とを有する経 路探索方法。
11. 前記経路コスト算出工程では、 前記始点から前記終点までの経 路コストを当該経路を構成するエッジのコストの和として算出する ことを特徴とする請求項 1 0記載の経路探索方法。
12. 前記経路コスト算出工程では、 前記第 1の距離及び前記第 2の 距離、 又は （第 1の距離一第 2の距離） で求まるコストが格納された データベースを参照して前記始点から前記終点までのコストを算出す る
ことを特徴とする請求項 1 0記載の経路探索方法。
13. 前記第 1の距離及び前記第 2の距離、 又は （前記第 1の距離一 前記第 2の距離） を算出して前記データベースを構築するデータべ一 ス生成工程を更に有する
ことを特徴とする請求項 1 2記載の経路探索方法。
14. 前記経路コスト算出工程では、 前記始点からのノード数が前記 所定数になるまでは、 前記始点からのコストを当該始点からの距離と する
ことを特徴とする請求項 1 0乃至 1 3のいずれか 1項記載の経路探 索方法。
15. ダリッドで表された領域に含まれる始点から終点までの経路の うち、 そのコストが最小のものを選択する経路探索方法であって、 各グリッドをノードとし、 前記始点の 8近傍の隣接ノードにエッジ を延ばし、 当該始点から前記隣接ノードまでの距離を当該隣接ノード のコストとして算出する第 1工程と、
前記始点から一のノードまでのコストを当該一のノードのコストと したとき、 エッジの先端に位置する先端ノードのうち、 ノードのコス トが最小のノードを注目ノードとし、 当該注目ノードの少なくとも前 方、 斜め右前、 及び斜め左前に位置する隣接ノードまでエッジを延ば し、 当該隣接ノードのコストを算出する第 2工程と、
当該隣接ノードが前記終点の場合、 前記始点から前記終点までのコ ストが最小の経路を選択する第 3工程とを有し、
前記隣接ノ一ドが前記終点となるまで前記第 2工程を繰り返すもの であって、
前記第 2工程は、
前記注目ノードから経路に沿って始点方向に所定数さかのぼつたノ ードを基準ノードとしたとき、 当該基準ノードから前記隣接ノードま での最短距離を示す第 1の距離、 及び前記基準ノ一ドから前記注目ノ 一ドまでの最短距離を示す第 2の距離を算出し、 又はデータベースか ら読み出す距離準備工程と、
前記注目ノードから前記隣接ノードへ伸びるエッジのコストを （前 記第 1の距離一第 2の距離） として算出するエッジコスト算出工程と 前記始点から前記隣接ノードまでの経路コストを当該経路を構成す るエッジのコストの和として算出する経路コスト算出工程とを有する 経路探索方法。
16. 移動手段と、
前記移動手段を駆動する駆動手段と、
周囲の環境をグリッドで表し、 当該ダリッド空間に含まれる始点か ら終点までの経路のうち、 そのコストが最小のものを選択する経路探 索手段と、
前記経路探索手段の経路探索結果に基づき前記駆動手段を制御する 制御手段とを備え、
前記経路探索手段は、
各グリッドをノードとし、 現在注目する注目ノードからこれに隣接 する隣接ノードへ伸ばしたエッジのコストを、 当該注目ノードから経 路に沿って前記始点方向に所定数さかのぼったノードを基準ノードと し、
(当該基準ノードから前記隣接ノードまでの最短距離を示す第 1の距 離） 一 （前記基準ノードから前記注目ノードまでの最短距離を示す第
2の距離）
として求めた値とし、 前記始点から前記終点までの経路コストを算出 する経路コスト算出手段と、
当該経路コストに応じて経路を決定する経路決定手段とを有する移 動体。
PCT/JP2008/062543 2007-07-18 2008-07-04 経路計画装置及び方法、コスト評価装置、並びに移動体 Ceased WO2009011295A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
CN2008800251799A CN101755247B (zh) 2007-07-18 2008-07-04 路径探索装置及方法、成本评估装置、以及移动体
US12/442,234 US8280574B2 (en) 2007-07-18 2008-07-04 Path planning device and method, cost evaluation device, and moving body
EP08778064.9A EP2172825B1 (en) 2007-07-18 2008-07-04 Route planning device and method, cost evaluation device and mobile body

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2007-187100 2007-07-18
JP2007187100A JP4661838B2 (ja) 2007-07-18 2007-07-18 経路計画装置及び方法、コスト評価装置、並びに移動体

Publications (1)

Publication Number Publication Date
WO2009011295A1 true WO2009011295A1 (ja) 2009-01-22

Family

ID=40259628

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2008/062543 Ceased WO2009011295A1 (ja) 2007-07-18 2008-07-04 経路計画装置及び方法、コスト評価装置、並びに移動体

Country Status (5)

Country Link
US (1) US8280574B2 (ja)
EP (1) EP2172825B1 (ja)
JP (1) JP4661838B2 (ja)
CN (1) CN101755247B (ja)
WO (1) WO2009011295A1 (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2010257115A (ja) * 2009-04-23 2010-11-11 Toyota Motor Corp 経路探索装置、経路探索方法、及び自律移動体
US20120109420A1 (en) * 2010-11-01 2012-05-03 Samsung Electronics Co., Ltd. Apparatus and method with mobile relocation
CN105043401A (zh) * 2015-07-14 2015-11-11 南京理工大学 基于浮动车法的城市健康出行规划方法及系统
CN110146090A (zh) * 2019-06-26 2019-08-20 张收英 机器人靠右行走导航方法和机器人
CN118428575A (zh) * 2024-07-04 2024-08-02 吉林省恒京自动化科技有限公司 一种智能机器人搬运作业路径规划优化方法

Families Citing this family (113)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20090105939A1 (en) * 2007-10-22 2009-04-23 Toyota Motor Engineering & Manufacturing North America, Inc. Vehicle navigation system with obstacle avoidance
JP4978494B2 (ja) * 2008-02-07 2012-07-18 トヨタ自動車株式会社 自律移動体、及びその制御方法
WO2010004744A1 (ja) * 2008-07-09 2010-01-14 パナソニック株式会社 経路危険性評価装置
WO2011064821A1 (ja) * 2009-11-27 2011-06-03 トヨタ自動車株式会社 自律移動体及びその制御方法
JP5381679B2 (ja) * 2009-12-16 2014-01-08 トヨタ自動車株式会社 経路探索システム、方法、プログラム、並びに移動体
US9157745B2 (en) * 2010-01-14 2015-10-13 Qualcomm Incorporated Scalable routing for mobile station navigation with location context identifier
CN102804240B (zh) * 2010-03-17 2015-10-14 日本电气株式会社 调度系统和方法
JP2011227807A (ja) * 2010-04-22 2011-11-10 Toyota Motor Corp 経路探索システム、経路探索方法、及び移動体
US8825388B2 (en) * 2010-07-13 2014-09-02 Qualcomm Incorporated Indoor likelihood heatmap
KR101234371B1 (ko) * 2010-12-21 2013-02-18 고려대학교 산학협력단 이동 로봇의 최적 경로 생성 방법 및 이를 이용한 이동 로봇
US8700638B2 (en) * 2011-03-08 2014-04-15 Libera, Inc. Computer-implemented weighted tree search to resolve variable name ambiguity
JP5831356B2 (ja) * 2012-05-15 2015-12-09 トヨタ自動車株式会社 移動体の経路計画方法
JP5926637B2 (ja) * 2012-07-10 2016-05-25 富士重工業株式会社 回避経路導出装置、回避経路導出プログラム、および、回避経路導出方法
US9292629B2 (en) * 2012-07-27 2016-03-22 Autodesk, Inc. Building path identification
US9120485B1 (en) 2012-09-14 2015-09-01 Google Inc. Methods and systems for smooth trajectory generation for a self-driving vehicle
US9488489B2 (en) 2012-09-28 2016-11-08 Google Inc. Personalized mapping with photo tours
TWM451103U (zh) * 2012-10-30 2013-04-21 Agait Technology Corp 行走裝置
JP5698865B2 (ja) 2013-03-12 2015-04-08 株式会社東芝 データベースシステム、プログラムおよびデータ処理方法
DE102013207899A1 (de) * 2013-04-30 2014-10-30 Kuka Laboratories Gmbh Fahrerloses Transportfahrzeug, System mit einem Rechner und einem fahrerlosen Transportfahrzeug, Verfahren zum Planen einer virtuellen Spur und Verfahren zum Betreiben eines fahrerlosen Transportfahrzeugs
DE102013207895A1 (de) * 2013-04-30 2014-10-30 Kuka Laboratories Gmbh Fahrerloses Transportfahrzeug, System mit einem Rechner und einem fahrerlosen Transportfahrzeug, Verfahren zum Betreiben eines fahrerlosen Transportfahrzeugs
WO2015025384A1 (ja) 2013-08-21 2015-02-26 株式会社東芝 データベースシステム、プログラムおよびデータ処理方法
WO2015029139A1 (ja) * 2013-08-27 2015-03-05 株式会社東芝 データベースシステム、プログラムおよびデータ処理方法
US9244940B1 (en) 2013-09-27 2016-01-26 Google Inc. Navigation paths for panorama
US9189839B1 (en) 2014-04-24 2015-11-17 Google Inc. Automatically generating panorama tours
US9002647B1 (en) 2014-06-27 2015-04-07 Google Inc. Generating turn-by-turn direction previews
US9418472B2 (en) 2014-07-17 2016-08-16 Google Inc. Blending between street view and earth view
JP2016024766A (ja) * 2014-07-24 2016-02-08 日本精工株式会社 案内用ロボット
EP3201709B1 (en) 2014-09-30 2021-03-17 NEC Corporation Method and system for determining a path of an object for moving from a starting state to an end state set avoiding one or more obstacles
CN104407613B (zh) * 2014-10-20 2017-03-22 河南工业职业技术学院 一种避障路径平滑优化方法
US9788481B2 (en) 2014-10-28 2017-10-17 Deere & Company Robotic mower navigation system
CN104599588B (zh) * 2015-02-13 2017-06-23 中国北方车辆研究所 一种栅格地图通行成本的计算方法
CN104808671B (zh) * 2015-05-19 2017-03-15 东南大学 一种家居环境下的机器人路径规划方法
US10209063B2 (en) * 2015-10-03 2019-02-19 X Development Llc Using sensor-based observations of agents in an environment to estimate the pose of an object in the environment and to estimate an uncertainty measure for the pose
US9764470B2 (en) * 2015-10-05 2017-09-19 X Development Llc Selective deployment of robots to perform mapping
US10093021B2 (en) * 2015-12-02 2018-10-09 Qualcomm Incorporated Simultaneous mapping and planning by a robot
CN105547310B (zh) * 2015-12-09 2018-10-02 南京理工大学 一种基于pm2.5健康出行的路径规划装置及方法
US10705528B2 (en) * 2015-12-15 2020-07-07 Qualcomm Incorporated Autonomous visual navigation
CN105716622B (zh) * 2016-04-12 2019-06-04 玉环看知信息科技有限公司 一种导航方法及导航服务器
WO2017186746A1 (en) 2016-04-26 2017-11-02 Ocado Innovation Limited Method of improving visual recognition of an item and item display system
US10054454B2 (en) * 2016-05-06 2018-08-21 Ford Global Technologies, Llc Network based storage of vehicle and infrastructure data for optimizing vehicle routing
US10207704B2 (en) * 2016-08-19 2019-02-19 Dura Operating, Llc Method for autonomously parking and un-parking a motor vehicle
US9896091B1 (en) * 2016-08-19 2018-02-20 Ohio State Innovation Foundation Optimized path planner for an autonomous valet parking system for a motor vehicle
US11042161B2 (en) 2016-11-16 2021-06-22 Symbol Technologies, Llc Navigation control method and apparatus in a mobile automation system
WO2018108178A1 (zh) * 2016-12-15 2018-06-21 苏州宝时得电动工具有限公司 自移动设备的回归方法、自移动设备、存储介质和服务器
CN108334062B (zh) * 2017-01-18 2020-12-04 华为技术有限公司 路径规划方法和装置
US10293485B2 (en) * 2017-03-30 2019-05-21 Brain Corporation Systems and methods for robotic path planning
CN107677285B (zh) 2017-04-11 2019-05-28 平安科技（深圳）有限公司 机器人的路径规划系统及方法
US11449059B2 (en) 2017-05-01 2022-09-20 Symbol Technologies, Llc Obstacle detection for a mobile automation apparatus
CN110603533A (zh) 2017-05-01 2019-12-20 讯宝科技有限责任公司 用于对象状态检测的方法和装置
US10726273B2 (en) 2017-05-01 2020-07-28 Symbol Technologies, Llc Method and apparatus for shelf feature and object placement detection from shelf images
US10949798B2 (en) 2017-05-01 2021-03-16 Symbol Technologies, Llc Multimodal localization and mapping for a mobile automation apparatus
WO2018204342A1 (en) 2017-05-01 2018-11-08 Symbol Technologies, Llc Product status detection system
US11367092B2 (en) 2017-05-01 2022-06-21 Symbol Technologies, Llc Method and apparatus for extracting and processing price text from an image set
WO2018201423A1 (en) 2017-05-05 2018-11-08 Symbol Technologies, Llc Method and apparatus for detecting and interpreting price label text
WO2019152263A1 (en) * 2018-01-30 2019-08-08 Fisher Controls International Llc Balanced trim regulator
JP2019174177A (ja) * 2018-03-27 2019-10-10 トヨタ自動車株式会社 移動量検出装置
JP6863325B2 (ja) * 2018-03-29 2021-04-21 株式会社豊田自動織機 清掃ロボットの走行経路生成装置
US10740911B2 (en) 2018-04-05 2020-08-11 Symbol Technologies, Llc Method, system and apparatus for correcting translucency artifacts in data representing a support structure
US11327504B2 (en) 2018-04-05 2022-05-10 Symbol Technologies, Llc Method, system and apparatus for mobile automation apparatus localization
US10809078B2 (en) * 2018-04-05 2020-10-20 Symbol Technologies, Llc Method, system and apparatus for dynamic path generation
US10832436B2 (en) 2018-04-05 2020-11-10 Symbol Technologies, Llc Method, system and apparatus for recovering label positions
US10823572B2 (en) 2018-04-05 2020-11-03 Symbol Technologies, Llc Method, system and apparatus for generating navigational data
US11454981B1 (en) * 2018-04-20 2022-09-27 AI Incorporated Versatile mobile robotic device
CN108827309B (zh) * 2018-06-29 2021-08-17 炬大科技有限公司 一种机器人路径规划方法及具有它的吸尘器
CN109240301B (zh) * 2018-09-28 2024-06-21 北京奇虎科技有限公司 扫地机器人路线规划方法、装置及扫地机器人
US11506483B2 (en) 2018-10-05 2022-11-22 Zebra Technologies Corporation Method, system and apparatus for support structure depth determination
US11010920B2 (en) 2018-10-05 2021-05-18 Zebra Technologies Corporation Method, system and apparatus for object detection in point clouds
GB2578721A (en) * 2018-11-05 2020-05-27 Continental Automotive Gmbh Method and system for processing image data utilizing deep neural network
US11090811B2 (en) 2018-11-13 2021-08-17 Zebra Technologies Corporation Method and apparatus for labeling of support structures
US11003188B2 (en) 2018-11-13 2021-05-11 Zebra Technologies Corporation Method, system and apparatus for obstacle handling in navigational path generation
US11079240B2 (en) 2018-12-07 2021-08-03 Zebra Technologies Corporation Method, system and apparatus for adaptive particle filter localization
US11416000B2 (en) 2018-12-07 2022-08-16 Zebra Technologies Corporation Method and apparatus for navigational ray tracing
US11100303B2 (en) 2018-12-10 2021-08-24 Zebra Technologies Corporation Method, system and apparatus for auxiliary label detection and association
US11015938B2 (en) 2018-12-12 2021-05-25 Zebra Technologies Corporation Method, system and apparatus for navigational assistance
US10731970B2 (en) 2018-12-13 2020-08-04 Zebra Technologies Corporation Method, system and apparatus for support structure detection
KR102749960B1 (ko) * 2018-12-26 2025-01-03 삼성전자주식회사 청소 로봇 및 그의 태스크 수행 방법
CA3028708C (en) 2018-12-28 2025-12-09 Zebra Technologies Corporation Method, system and apparatus for dynamic loop closure in mapping trajectories
WO2020144970A1 (ja) * 2019-01-11 2020-07-16 ソニー株式会社 行動計画装置、行動計画方法、及びプログラム
JP7243260B2 (ja) * 2019-02-14 2023-03-22 株式会社タダノ クレーンおよびクレーンの経路生成システム
JP7247634B2 (ja) * 2019-02-14 2023-03-29 株式会社タダノ クレーンおよびクレーンの経路生成システム
JP7159899B2 (ja) * 2019-02-14 2022-10-25 株式会社タダノ クレーンおよびクレーンの経路生成システム
JP7310164B2 (ja) * 2019-02-14 2023-07-19 株式会社タダノ クレーン及び経路生成システム
JP7167759B2 (ja) * 2019-02-14 2022-11-09 株式会社タダノ クレーンおよびクレーンの経路生成システム
CN109978243A (zh) * 2019-03-12 2019-07-05 北京百度网讯科技有限公司 车辆轨迹规划方法、装置、计算机设备、计算机存储介质
CN109917794B (zh) * 2019-04-18 2022-02-18 北京智行者科技有限公司 全局路径规划方法及装置
US11402846B2 (en) 2019-06-03 2022-08-02 Zebra Technologies Corporation Method, system and apparatus for mitigating data capture light leakage
US11200677B2 (en) 2019-06-03 2021-12-14 Zebra Technologies Corporation Method, system and apparatus for shelf edge detection
US11662739B2 (en) 2019-06-03 2023-05-30 Zebra Technologies Corporation Method, system and apparatus for adaptive ceiling-based localization
US11341663B2 (en) 2019-06-03 2022-05-24 Zebra Technologies Corporation Method, system and apparatus for detecting support structure obstructions
US11960286B2 (en) 2019-06-03 2024-04-16 Zebra Technologies Corporation Method, system and apparatus for dynamic task sequencing
US11080566B2 (en) 2019-06-03 2021-08-03 Zebra Technologies Corporation Method, system and apparatus for gap detection in support structures with peg regions
US11151743B2 (en) 2019-06-03 2021-10-19 Zebra Technologies Corporation Method, system and apparatus for end of aisle detection
JP6711949B2 (ja) * 2019-08-01 2020-06-17 エヌイーシー ラボラトリーズ ヨーロッパ ゲーエムベーハー １個以上の障害物を回避して始状態から終状態集合まで移動する物体の経路を決定する方法およびシステム
EP3816758B1 (en) * 2019-10-17 2024-01-17 Nokia Solutions and Networks Oy Grid-based movement control
CN111006666B (zh) * 2019-11-21 2021-10-29 深圳市优必选科技股份有限公司 机器人路径规划方法、装置、存储介质和机器人
US11507103B2 (en) 2019-12-04 2022-11-22 Zebra Technologies Corporation Method, system and apparatus for localization-based historical obstacle handling
US11107238B2 (en) 2019-12-13 2021-08-31 Zebra Technologies Corporation Method, system and apparatus for detecting item facings
CN113448324B (zh) * 2020-03-09 2023-08-04 北京合众思壮科技股份有限公司 路径规划方法、装置、电子设备和存储介质
US11822333B2 (en) 2020-03-30 2023-11-21 Zebra Technologies Corporation Method, system and apparatus for data capture illumination control
CN113537672B (zh) * 2020-04-15 2024-11-05 北京旷视机器人技术有限公司 任务分配方法、任务分配装置、介质及电子设备
US20210401500A1 (en) * 2020-06-29 2021-12-30 Biosense Webster (Israel) Ltd. Efficient automatic finding of minimal ear-nose-throat (ent) path for probe
US11450024B2 (en) 2020-07-17 2022-09-20 Zebra Technologies Corporation Mixed depth object detection
US11593915B2 (en) 2020-10-21 2023-02-28 Zebra Technologies Corporation Parallax-tolerant panoramic image generation
US11392891B2 (en) 2020-11-03 2022-07-19 Zebra Technologies Corporation Item placement detection and optimization in material handling systems
US11847832B2 (en) 2020-11-11 2023-12-19 Zebra Technologies Corporation Object classification for autonomous navigation systems
GB2606752A (en) * 2021-05-20 2022-11-23 Continental Automotive Gmbh Robot fleet management method and system using a graph neural network
US11954882B2 (en) 2021-06-17 2024-04-09 Zebra Technologies Corporation Feature-based georegistration for mobile computing devices
US11906314B2 (en) * 2021-09-10 2024-02-20 Nec Corporation System for waypoint selection and method of using
US12154059B2 (en) * 2021-12-07 2024-11-26 Here Global B.V. Territory set determination based on historical service event data
CN114895661A (zh) * 2021-12-14 2022-08-12 合肥哈工轩辕智能科技有限公司 一种智能驾驶场景下的实时路径规划方法及装置
CN114355901B (zh) * 2021-12-17 2023-06-20 华南理工大学 一种路径规划智能优化方法、装置、电子设备和存储介质
US12493294B2 (en) * 2023-02-16 2025-12-09 Dell Products L.P. Managing object routing in computing environments
KR102917390B1 (ko) * 2025-07-22 2026-01-23 주식회사 핑크랩 공간 내 환경 정보에 따른 그리드 기반 경로 생성 및 로봇의 이동 제어 방법, 장치 및 시스템

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH06289929A (ja) * 1993-04-02 1994-10-18 Shinko Electric Co Ltd 最適経路決定装置
JP2001324343A (ja) * 2000-05-17 2001-11-22 Alpine Electronics Inc 経路探索方法
US20060167601A1 (en) 2004-12-17 2006-07-27 Eads Deutschland Gmbh Method and apparatus for determining optimized paths of a vehicle

Family Cites Families (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE69415067T2 (de) * 1993-04-02 1999-07-08 Shinko Electric Co., Ltd., Tokio/Tokyo Methode und Steuervorrichtung für ein Transportverwaltungssystem mit fahrerlosen Fahrzeugen
US6067572A (en) * 1996-11-07 2000-05-23 Novell, Inc. Extrinsically influenced near-optimal path apparatus and method
US6098107A (en) * 1997-10-31 2000-08-01 Lucent Technologies Inc. Dynamic algorithms for shortest path tree computation
US6259988B1 (en) * 1998-07-20 2001-07-10 Lockheed Martin Corporation Real-time mission adaptable route planner
SE0100924D0 (sv) * 2001-03-15 2001-03-15 Electrolux Ab Energy-efficient navigation of an autonomous surface treatment apparatus
JP3841401B2 (ja) * 2001-09-26 2006-11-01 株式会社東芝 構内案内装置、サーバ装置およびプログラム
JP4076905B2 (ja) * 2003-05-15 2008-04-16 アルパイン株式会社 ナビゲーション装置
JP4251545B2 (ja) 2003-07-11 2009-04-08 独立行政法人科学技術振興機構 移動ロボット用経路計画システム
US7079943B2 (en) * 2003-10-07 2006-07-18 Deere & Company Point-to-point path planning
SE0303576D0 (sv) * 2003-12-23 2003-12-23 Ericsson Telefon Ab L M Cost determination in a multihop network
KR100745975B1 (ko) 2004-12-30 2007-08-06 삼성전자주식회사 그리드 맵을 사용하여 최소 이동 경로로 이동하는 방법 및장치
US7869946B2 (en) * 2005-02-04 2011-01-11 Microsoft Corporation Efficient navigation routing system and method
JP2007316966A (ja) * 2006-05-26 2007-12-06 Fujitsu Ltd 移動ロボット、その制御方法及びプログラム
WO2008089364A1 (en) * 2007-01-17 2008-07-24 Weidner David P Multi-level path mapping for street grid and non-street grid entities
JP2009025898A (ja) * 2007-07-17 2009-02-05 Toyota Motor Corp 経路計画装置、経路計画方法及び移動体

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH06289929A (ja) * 1993-04-02 1994-10-18 Shinko Electric Co Ltd 最適経路決定装置
JP2001324343A (ja) * 2000-05-17 2001-11-22 Alpine Electronics Inc 経路探索方法
US20060167601A1 (en) 2004-12-17 2006-07-27 Eads Deutschland Gmbh Method and apparatus for determining optimized paths of a vehicle

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP2172825A4

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2010257115A (ja) * 2009-04-23 2010-11-11 Toyota Motor Corp 経路探索装置、経路探索方法、及び自律移動体
US20120109420A1 (en) * 2010-11-01 2012-05-03 Samsung Electronics Co., Ltd. Apparatus and method with mobile relocation
US8594860B2 (en) * 2010-11-01 2013-11-26 Samsung Electronics Co., Ltd. Apparatus and method with mobile relocation
CN105043401A (zh) * 2015-07-14 2015-11-11 南京理工大学 基于浮动车法的城市健康出行规划方法及系统
CN105043401B (zh) * 2015-07-14 2018-04-03 南京理工大学 基于浮动车法的城市健康出行规划方法及系统
CN110146090A (zh) * 2019-06-26 2019-08-20 张收英 机器人靠右行走导航方法和机器人
CN118428575A (zh) * 2024-07-04 2024-08-02 吉林省恒京自动化科技有限公司 一种智能机器人搬运作业路径规划优化方法

Also Published As

Publication number Publication date
JP2009025974A (ja) 2009-02-05
US8280574B2 (en) 2012-10-02
CN101755247A (zh) 2010-06-23
CN101755247B (zh) 2012-03-21
EP2172825B1 (en) 2013-08-21
EP2172825A4 (en) 2011-04-27
US20100082194A1 (en) 2010-04-01
JP4661838B2 (ja) 2011-03-30
EP2172825A1 (en) 2010-04-07

Similar Documents

Publication Publication Date Title
JP4661838B2 (ja) 経路計画装置及び方法、コスト評価装置、並びに移動体
WO2009011296A1 (ja) 経路計画装置、経路計画方法及び移動体
US11554495B2 (en) Method of localization using multi sensor and robot implementing same
CN110352330B (zh) 用于自主交通工具的动作规划系统和方法
JP3945279B2 (ja) 障害物認識装置、障害物認識方法、及び障害物認識プログラム並びに移動型ロボット装置
JP5998816B2 (ja) 経路探索方法、経路探索装置、ロボット制御装置、ロボット及びプログラム
JP7476941B2 (ja) ロボット、ロボットの制御方法及びプログラム
JP2012064131A (ja) 地図生成装置、地図生成方法、移動体の移動方法、及びロボット装置
JP2003079685A (ja) 視覚障害者歩行用補助具
JP2004078316A (ja) 姿勢認識装置及び自律ロボット
JP2010231470A (ja) 情報提供システム
JP7058761B2 (ja) 移動体制御装置、移動体制御学習装置、及び移動体制御方法
CN110087450A (zh) 工作系统以及工作方法
CN119407392B (zh) 融合大模型的焊缝识别方法、装置、电子设备及存储介质
KR20190119234A (ko) 이동 로봇 및 그 제어방법
EP2610783A2 (en) Object recognition method and descriptor for object recognition
KR20200100019A (ko) 이동 로봇 및 그 제어방법
KR101270895B1 (ko) 주차 제어 방법 및 시스템
JP2008009999A (ja) 平面抽出方法、その装置、そのプログラム、その記録媒体及び撮像装置
JP2009178782A (ja) 移動体、環境地図生成装置、及び環境地図生成方法
JP5891553B2 (ja) ルートパースペクティブモデル構築方法およびロボット
JP2023005449A (ja) 経路決定システム、移動体、及び経路決定プログラム
JP5187563B2 (ja) 音響再生ロボット
JP2022142452A (ja) 制御装置、制御方法、およびプログラム
JP5157545B2 (ja) 全身協調装置、ロボット及びロボットの制御方法

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200880025179.9

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 08778064

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 12442234

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 2008778064

Country of ref document: EP