Search

EP-3894144-B1 - FPGA-BASED ACCELERATION USING OPENCL ON FCL IN ROBOT MOTION PLANNING

EP3894144B1EP 3894144 B1EP3894144 B1EP 3894144B1EP-3894144-B1

Inventors

  • WANG, DAWEI
  • LIU, LING
  • SHI, Xuesong
  • WANG, Chunjie
  • You, Ganmei

Dates

Publication Date
20260513
Application Date
20181212

Claims (13)

  1. An apparatus (100) comprising: a processor (102) configured to: initiate collision detection operations for a plurality of objects; and perform a first phase of the collision detection operations, wherein the first phase comprises a collision checking task to be performed for each pair of bodies to determine potential collision between the two bodies; a Field-Programmable Gate Array, FPGA, (104) comprising logic circuitry and a local memory (112), wherein the logic circuitry is coupled to the processor (102) and configured to: perform a second phase of the collision detection operations, wherein the second phase comprises a collision checking task for those pairs of bodies that failed to pass the first phase, wherein the second phase uses oriented bounding volumes, OBBs, having orientation parameters, center coordinates, and extents for three-dimensional placement, to detect collisions; and a first memory (108), coupled to the logic circuitry, configured to: store data corresponding to a plurality of OBBs indicating Bounding Volume, BV, models for the plurality of objects, wherein the processor (102) is configured to: transfer a portion of data stored in the first memory (108) to the local memory (112) of the FPGA (104) prior to performance of the collision detection operations; align each of the plurality of the OBBs to 64-byte; and wherein the local memory of the FPGA (104) is configured to cache at least a first 16 OBBs of each of the BV models; and wherein the logic circuitry is further configured to apply an algorithm optimization to sequentially pre-fetch data from the first memory (108) and utilize parallelism to unroll the collision detection operations to accelerate the second phase.
  2. The apparatus (100) of claim 1, wherein the local memory (112) is configured to store BV node identifier information.
  3. The apparatus (100) of any one of claims 1 to 2, wherein the processor (102) is configured to launch the second phase for processing by the logic circuitry after processing of the first phase has been completed by the processor (102).
  4. The apparatus (100) of any one of claims 1 to 3, wherein the logic circuitry is configured to execute one or more instructions on a Flexible Collision Library, FCL, to perform the collision detection operations.
  5. The apparatus (100) of any one of claims 1 to 4, wherein the logic circuitry and the processor (102) are coupled via an interconnect (110).
  6. The apparatus (100) of claim 5, wherein the interconnect (110) comprises a Peripheral Component Interconnect express, PCIe, interconnect.
  7. The apparatus (100) of any one of claims 1 to 6, wherein the first memory (108) or the local memory (112) comprise Random Access Memory, RAM, Dynamic RAM, DRAM, or Double Data Rate, DDR, memory.
  8. A robot comprising an apparatus according to any one of claims 1 to 7, wherein the logic circuitry is configured to accelerate collision detection operations for at least one arm of the robot.
  9. A method (300, 350) comprising: initiating (352), by means of a processor, collision detection operations for a plurality of objects; performing, by means of the processor, a first phase of the collision detection operations, wherein the first phase comprises a collision checking task to be performed for each pair of bodies to determine potential collision between the two bodies; accelerating, by means of logic circuitry of a Field-Programmable Gate Array, FPGA, coupled to the processor, the collision detection operations; performing, by means of the logic circuitry, a second phase of the collision detection operations, wherein the second phase comprises a collision checking task for those pairs of bodies that failed to pass the first phase, wherein the second phase uses oriented bounding volumes, OBBs, having orientation parameters, center coordinates, and extents for three-dimensional placement, to detect collisions; and storing, by means of a first memory, data corresponding to a plurality of OBBs indicating Bounding Volume, BV, models for the plurality of objects; and transferring (304), by means of the processor, a portion of data stored in the first memory to the local memory of the FPGA prior to performance of the collision detection operations; aligning, by means of the processor, each of the plurality of the OBBs to 64-byte; and caching, by means of the local memory of the FPGA, at least a first 16 OBBs of each of the BV models; and applying, by means of the logic circuitry, an algorithm optimization to sequentially pre-fetching data from the first memory (108) and utilizing parallelism to unrolling the collision detection operations accelerating the second phase.
  10. The method (300, 350) of claim 9, further comprising storing BV node identifier information.
  11. The method (300, 350) of any one of claims 9 to 10, further comprising, by means of the processor, launching the second phase for processing by the logic circuitry after processing of the first phase has been completed by the processor.
  12. The method (300, 350) of any one of claims 9 to 11, further comprising executing, by means of the logic circuitry, one or more instructions on a Flexible Collision Library, FCL, to perform the collision detection operations.
  13. Machine-readable storage including machine-readable instructions, when executed, cause the apparatus according to any one of claims 1 to 8 to implement the method according to any one of claims 9 to 12.

Description

FIELD The present disclosure generally relates to the field of electronics. More particularly, an embodiment relates to FPGA (Field-Programmable Gate Array) based acceleration in robot motion planning. BACKGROUND A fundamental robotics task is to plan collision-free motions for complex bodies from a start position to a goal position. As an example, "motion" and "path" planning was the most occurred keyword on International Conference on Intelligent Robots (IROS) 2017 (the most recent top tier conference on robotics). Document ZHANG ZHAORUI ET AL: "FPGA-Based High-Performance Collision Detection: An Enabling Technique for Image-Guided Robotic Surgery", FRONTIERS IN ROBOTICS AND AI, vol. 3, 31 August 2016 (2016-08-31), XP055931156, DOI: 10.3389/frobt.2016.00051 proposes to minimize the traversal complexity and to eliminate repetitive works in the Sweep and Prune algorithm used for speeding up collision detection on a CPU platform. Document LAUTERBACH C ET AL: "gProximity: Hierarchical GPU-based Operations for Collision and Distance Queries", COMPUTER GRAPHICS FORUM : JOURNAL OF THE EUROPEAN ASSOCIATION FOR COMPUTER GRAPHICS, WILEY-BLACKWELL, OXFORD, vol. 29, no. 2, 7 June 2010 (2010-06-07), pages 419-428, XP071486984, ISSN: 0167-7055, DOI: 10.1111/J.1467-8659.2009.01611.X proposes a novel parallel algorithm for collision detection and separation distance computation for rigid and deformable models that exploit the computational capabilities of many-core GPUs. Thread and data parallelism is performed for fast hierarchy construction, updating, and traversal using tight-fitting bounding volumes such as oriented bounding boxes and rectangular swept spheres. Document ALVES FREDY AUGUSTO M ET AL: "Designing a collision detection accelerator on a heterogeneous CPU-FPGA platform", 2017 INTERNATIONAL CONFERENCE ON RECONFIGURABLE COMPUTING AND FPGAS (RECONFIG), IEEE, 4 December 2017 (2017-12-04), pages 1-6, XP033313022, DOI: 10.1109/RECONFIG.2017.8279786 proposes a hardware accelerator implementation of the most fine-grained part of a collision detection. It shows that even small computational kernels can get speed improvements as the FPGA and CPU are more closely integrated. However, performing tasks associated with robot motion planning can be very compute intensive. As a result, acceleration of such tasks can improve the overall usability and functionality of robotic systems. BRIEF DESCRIPTION OF THE DRAWINGS The detailed description is provided with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference numbers in different figures indicates similar or identical items. Fig. 1 illustrates a block diagram of a system for FPGA-based acceleration in robot motion planning, according to an embodiment.Fig. 2 illustrates an Oriented Bounding Box (OBB) data structure, according to an embodiment.Fig. 3A illustrates a flow chart of a method for acceleration on an FPGA, according to an embodiment.Fig. 3B illustrates a flow chart of a method to perform BVH traverse function, according to one embodiment.Fig. 4 illustrates a map of the relationship between a Node Stack and external/main memory, according to an embodiment.Figs. 5 and 6 illustrates block diagrams of embodiments of computing systems, which may be utilized in various embodiments discussed herein.Figs. 7 and 8 illustrate various components of processers in accordance with some embodiments. DETAILED DESCRIPTION In the following description, numerous specific details are set forth in order to provide a thorough understanding of various embodiments. However, various embodiments may be practiced without the specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail so as not to obscure the particular embodiments. Further, various aspects of embodiments may be performed using various means, such as integrated semiconductor circuits ("hardware"), computer-readable instructions organized into one or more programs ("software"), or some combination of hardware and software. For the purposes of this disclosure reference to "logic" shall mean either hardware (such as logic circuitry or more generally circuitry or circuit), software, firmware, or some combination thereof. As mentioned above, one fundamental robotics task is to plan collision-free motions for complex bodies from a start position to a goal position. However, performing tasks associated with robot motion planning can be very compute intensive. One of the most common software stacks used for robot motion planning may include the combination of ROS (that refers to the Robot Operating System which includes a set of software libraries and tools that help in building robot applications), MoveIt! (which is a software platform used for mobile manipulation and motion planning), and FCL. FCL refers to Flexible Collis