TY - JOUR

T1 - FPR-Fast Path Risk Algorithm to Evaluate Collision Probability

AU - Blake, Andrew

AU - Bordallo, Alejandro

AU - Brestnichki, Kamen

AU - Hawasly, Majd

AU - Penkov, Svetlin Valentinov

AU - Ramamoorthy, Subramanian

AU - Silva, Alexandre

N1 - Publisher Copyright:
© 2016 IEEE.

PY - 2020/1

Y1 - 2020/1

N2 - As mobile robots and autonomous vehicles become increasingly prevalent in human-centred environments, there is a need to control the risk of collision. Perceptual modules, for example machine vision, provide uncertain estimates of object location. In that context, the frequently made assumption of an exactly known free-space is invalid. Clearly, no paths can be guaranteed to be collision free. Instead, it is necessary to compute the probabilistic risk of collision on any proposed path. The FPR algorithm, proposed here, efficiently calculates an upper bound on the risk of collision for a robot moving on the plane. That computation orders candidate trajectories according to (the bound on) their degree of risk. Then paths within a user-defined threshold of primary risk could be selected according to secondary criteria such as comfort and efficiency. The key contribution of this letter is the FPR algorithm and its 'convolution trick' to factor the integrals used to bound the risk of collision. As a consequence of the convolution trick, given K obstacles and N candidate paths, the computational load is reduced from the naive O(NK), to the qualitatively faster O(N+K).

AB - As mobile robots and autonomous vehicles become increasingly prevalent in human-centred environments, there is a need to control the risk of collision. Perceptual modules, for example machine vision, provide uncertain estimates of object location. In that context, the frequently made assumption of an exactly known free-space is invalid. Clearly, no paths can be guaranteed to be collision free. Instead, it is necessary to compute the probabilistic risk of collision on any proposed path. The FPR algorithm, proposed here, efficiently calculates an upper bound on the risk of collision for a robot moving on the plane. That computation orders candidate trajectories according to (the bound on) their degree of risk. Then paths within a user-defined threshold of primary risk could be selected according to secondary criteria such as comfort and efficiency. The key contribution of this letter is the FPR algorithm and its 'convolution trick' to factor the integrals used to bound the risk of collision. As a consequence of the convolution trick, given K obstacles and N candidate paths, the computational load is reduced from the naive O(NK), to the qualitatively faster O(N+K).

KW - Collision avoidance

KW - probability and statistical methods

UR - http://www.scopus.com/inward/record.url?scp=85072724750&partnerID=8YFLogxK

U2 - 10.1109/LRA.2019.2943074

DO - 10.1109/LRA.2019.2943074

M3 - Article

AN - SCOPUS:85072724750

SN - 2377-3766

VL - 5

SP - 1

EP - 7

JO - IEEE Robotics and Automation Letters

JF - IEEE Robotics and Automation Letters

IS - 1

M1 - 8846054

ER -