Path planning device, path planning method, and computer program

• US 8,185,265 B2
• Filed: 12/23/2009
• Issued: 05/22/2012
• Est. Priority Date: 01/01/2009
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.)
• Inventors: Nagano, Masakuni
• Primary Examiner(s): Trammell, James P
• Assistant Examiner(s): Marc, McDieunel
• Application Number:
  US12/645,841
• Publication Number:
  US 20100168950A1
• Time in Patent Office: 881 Days
• Field of Search: 700/259, 700/84, 700/177, 700/182, 700/185, 700/187, 700/188, 700/254, 700/302, 287/98, 340/573.7, 345/474, 381/381, 600/595, 356/394, 347/104, 347/2, 400/625, 400/573.7, 400/686.2, 400/988, 701/23, 701/25, 701/213, 701/217, 701/221, 701/301, 355/67, 355/53, 355/66, 355/71, 355/77, 271/126, 271/145, 271/188, 271/288, 271/273, 271/3.01, 134/62, 134/63, 134/66, 134/69, 134/78, 134/80, 134/84, 134/85, 134/86, 134/89, 156/361, 156/483, 156/485, 156/542, 180/167, 180/169, 192/218, 209/900, 209/93, 297/14, 297/40, 297/41, 297/43, 318/587, 34/92, 342/28, 342/455, 342/457, 250/226, 270/21.1, 154/14, 221/226
• US Class Current: 701/25
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones

Abstract

A path planning device includes: an initial position and posture path acquiring unit which acquires an initial position and posture path including a plurality of nodes connecting present position and posture of a control target to target position and posture and which configures a rigid body corresponding to the control target in each node in the position and posture path; an interference detector which detects interference with the control target by an obstruction; an external force calculator which calculates an external force for each rigid body; and a multi rigid body system dynamics simulation unit which performs a multi rigid body system dynamics simulation on a plurality of equations of rigid body motion and which acquires positions and postures of the control target at times corresponding to the nodes in the position and posture path.

Claims

1. A path planning device for planning a position and posture path of a control target in a motion space from a present position and posture to a target position and posture, comprising:

an initial position and posture path acquiring unit which acquires an initial position and posture path including a plurality of nodes connecting the present position and posture of the control target to the target position and posture, and which configures a rigid body corresponding to the control target in each node in the position and posture path;

an interference detector which detects an interference with the control target in the position and posture path by an obstruction existing in the motion space;

an external force calculator which calculates external forces for each of a plurality of rigid bodies based on a dynamic model that uses the external forces to express a requirement for smoothing the position and posture path and for avoiding the interference by the obstruction, the dynamic model modeling each of the plurality of rigid bodies as a virtue rigid body plane not having a volume; and

a multi rigid body system dynamics simulation unit which performs a multi rigid body system dynamics simulation on a plurality of equations of rigid body motion representing coupled motions of the plurality of rigid bodies on which the external forces calculated by the external force calculator act, respectively, and which acquires positions and postures of the control target at times corresponding to the nodes in the position and posture path on a basis of positions and postures of the rigid bodies when the path is convergent to a predetermined state.

2. The path planning device according to claim 1, wherein the initial position and posture path acquiring unit acquires a path between the present position of the control target and the target position on a basis of a search tree branched into a plurality of routes to the plurality of nodes and developed in the motion space, and wherein the initial position and posture path acquiring unit gives an initial posture to each of the rigid bodies located at each node.

3. The path planning device according to claim 1, wherein the interference detector applies a GJK algorithm (Gilbert-Johnson-Keerthi distance algorithm) to detect a shortest distance between each rigid body and the obstruction.

4. The path planning device according to claim 1, wherein the external force calculator uses the dynamical model in which the virtual rigid body plane fixed in a local coordinate system of each rigid body is defined and corresponding vertexes of neighboring virtual rigid body planes are connected to each other by springs having a predetermined spring constant and dampers having a predetermined damping constant to calculate, as the external forces expressing the requirement for smoothing the position and posture path, an inter-rigid-body force which is a sum of spring forces and damper forces acting between vertexes of one virtual rigid body plane and corresponding vertexes of a neighboring virtual rigid body plane and a rotational moment, which acts on the rigid body, about an origin of a global coordinate system including a sum of moments acting on the vertexes of each virtual rigid body due to the spring forces and the damper forces.

5. The path planning device according to claim 1, wherein the interference detector detects a shortest distance between each rigid body located at each node in the position and posture path and the obstruction, and

wherein the external force calculator calculates a repulsive force acting on each rigid body depending on the shortest distance as an external force expressing the requirement for causing the position and posture path to avoid the interference by the obstruction.

6. The path planning device according to claim 1, wherein the external force calculator calculates a moment corresponding to an angle formed by a forward moving direction of each rigid body fixed in a local coordinate system of the rigid body and a direction of the position and posture path between neighboring rigid bodies as the external force expressing a requirement for approaching an ideal position and posture path.

7. A path planning method of planning a position and posture path of a control target in a motion space from a present position and posture to a target position and posture, comprising the steps of:

acquiring, by an initial position and posture path acquiring unit, an initial position and posture path including a plurality of nodes connecting the present position and posture of the control target to the target position and posture and configuring a rigid body corresponding to the control target in each node in the position and posture path;

detecting, by an interference detector, an interference with the control target in the position and posture path by an obstruction existing in the motion space;

calculating, by a processor, external forces for each of a plurality of rigid bodies based on a dynamic model that uses external forces to express a requirement for smoothing the position and posture path and for avoiding the interference by the obstruction, the dynamic model modeling each of the plurality of rigid bodies as a virtue rigid body plane not having a volume; and

performing, by the processor, a multi rigid body system dynamics simulation on a plurality of equations of rigid body motion representing coupled motions of the plurality of rigid bodies on which the calculated external forces act, respectively, and acquiring positions and postures of the control target at times corresponding to the nodes in the position and posture path on a basis of positions and postures of the rigid bodies when the path is convergent to a predetermined state.

8. A non-transitory computer readable storage medium encoded with a computer program which, when executed on a computer, causes the computer to perform processes of planning a position and posture path of a control target in a motion space from a present position and posture to a target position and posture, the computer program causing the computer to serve as:

an initial position and posture path acquiring unit which acquires an initial position and posture path including a plurality of nodes connecting the present position and posture of the control target to the target position and posture and which configures a rigid body corresponding to the control target in each node in the position and posture path;

an interference detector which detects an interference with the control target in the position and posture path by an obstruction existing in the motion space;

an external force calculator which calculates external forces for each of a plurality of rigid bodies based on a dynamic model that uses the external forces to express a requirement for smoothing the position and posture path and for avoiding interference by the obstruction, the dynamic model modeling each of the plurality of rigid bodies as a virtue rigid body plane not having a volume; and

a multi rigid body system dynamics simulation unit which performs a multi rigid body system dynamics simulation on a plurality of equations of rigid body motion representing coupled motions of the plurality of rigid bodies on which the external forces calculated by the external force calculator act, respectively, and which acquires positions and postures of the control target at times corresponding to the nodes in the position and posture path on a basis of the positions and postures of the rigid bodies when the path is convergent to a predetermined state.