IEEE Circuits and Systems Magazine - Q2 2021 - 61

queries in complex environments without reprogramming
the accelerator during runtime.
C. Collision Detection
In the collision detection step, the planner determines
whether there are potential collisions with the environment
or the robot itself during movement. Specifically,
collision detection is the primary challenge in motion
planning, which often comprises 90% of the processing
time [165].
Several works leverage data parallelization computing
on GPUs to achieve speedup [165]-[167]. For example,
Bialkowski et al. [165] divide the RRT* algorithm
of collision detection tasks into three parallel dimensions
and construct thread block grids to execute collision
computations simultaneously. However, GPU
can only provide a constant speedup factor due to the
core limitations, which is still hard to achieve the realtime
requirement.
Recently, [168]-[170] develop high-efficiency custom
hardware implementations based on the FPGA system.
Atay and Bayazit [168] focus on directly accelerating the
PRM algorithm on FPGA by creating functional units to
perform the random sampling, nearest neighbor search
and parallelizing triangle-triangle testing. However,
this design cannot be reconfigured at runtime, and the
huge resource demands make it fail to support a large
roadmap. Murray et al. [169] present a novel microarchitecture
for an FPGA-based accelerator to speed up
collision detection by creating a specialized circuit for
each motion in the roadmap. This solution achieves
sub-millisecond speed for motion planning query and
improves the power consumption by more than one order
of magnitude, which is sufficient to enable real-time
robotics applications.
Besides real-time constraint, motion planning algorithms
also have flexibility requirements to make the
robots adapt to dynamic environments. Dadu-P [170]
build a scalable motion planning accelerator to attain
both high efficiency and flexibility, where a motion
plan can be solved in around 300 microseconds in a
dynamic environment. A hardware-friendly data structure
representing roadmap edges is adopted to achieve
flexibility, and a batched processing as well as a priority-rating
method are proposed to achieve high efficiency.
But this design comprises a 25× latency increase to
make it retargetable to different robots and scenarios
due to the external memory access. Murray et al. [164]
develop a fully retargetable microarchitecture of collision
detection and graph search accelerator that can
perform motion planning in less than 3 ms with a modest
power consumption of 35 W. This design divides
the collision detection workflow into two stages. The
SECOND QUARTER 2021
collision detection results for the discretized roadmap
are precomputed in the first stage before runtime, and
then the collision detection accelerator streams in the
voxels of obstacles and the edges of flags which are in
collision at runtime.
D. Graph Search
After collision detection, the planner will try to find the
shortest and safe path from the start position to the
target position based on the obtained collision-free
roadmap through graph search. Several works explore
graph search accelerations. Bondhugula et al. [171]
employ a parallel FPGA-based design using a blocked
algorithm to solve large instances of All-Pairs ShortestPaths
(APSP) problem, which achieves a 15× speedup
over an optimized CPU-based implementation. Sridharan
et al. [172] present an architecture-efficient solution
based on Dijkstra's algorithm to accelerate the
shortest path search, and Takei et al. [173] extend this
for a high degree of parallelism and large-scale graph
search. Recently, Murray et al. [164] accelerate graph
search with the Bellman-Ford algorithm. By leveraging
a precomputed roadmap and bounding specific robot
quantities, this design enables a more compact and efficient
storage structure, dataflows and a low-cost interconnection
network.
VI. Partial Reconfiguration
FPGA technology provides the flexibility of on-site programming
and re-programming without going through
re-fabrication with a modified design. Partial Reconfiguration
(PR) takes this flexibility one step further,
allowing the modification of an operating FPGA
design by loading a partial configuration file, usually
a partial BIT file [174]. Using PR, after a full BIT
file configures the FPGA, partial BIT files can be downloaded
to modify reconfigurable regions in the FPGA
without compromising the integrity of the applications
running on those parts of the device that are
not being reconfigured.
A major performance bottleneck for PR is the configuration
overhead, which seriously limits the usefulness
of PR. To address this problem, in [175], the authors
propose a combination of two techniques to minimize
the overhead. First, the authors design and implement
fully streaming DMA engines to saturate the configuration
throughput. Second, the authors exploit a simple
form of data redundancy to compress the configuration
bitstreams, and implement an intelligent internal
configuration access port (ICAP) controller to perform
decompression at runtime. This design achieves an effective
configuration data transfer throughput of up to
1.2 Gbytes/s, which actually well surpasses the theoretical
IEEE CIRCUITS AND SYSTEMS MAGAZINE
61
IEEE Circuits and Systems Magazine - Q2 2021

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2021
