Real-time Safety-guaranteed Trajectory Planning using Hamilton-Jacobi Reachability Analysis

Abstract

Guaranteeing safety in planning trajectories of robotic systems is a fundamental requirement for reliable operation. However, it is difficult to verify in advance whether the seemingly-safe planned trajectory will be safe because of unknown disturbances exerted to the system during the actual runtime. This dissertation presents a real-time safety-guaranteed trajectory planning algorithm. The safety of the system can be guaranteed by the forward reachable sets (FRSs) computed from the Hamilton-Jacobi (HJ) reachability analysis. Considering that the unexpected disturbance can instantaneously drive the system to devastating situations, this work concentrates on real-time safety verification. The proposed reachability analysis consists of 2 stages: the analysis of the linearized (time-varying) dynamics, and nonlinear dynamics that is polynomial of states and disturbances. For the reachability analysis on linear time-varying (LTV) systems, this work presents an ellipsoidal approximation of the FRS based on the generalized Hopf formula. Since the formula gives the explicit solution of the Hamilton-Jacobi-Bellman (HJB) equation, the proposed ellipsoidal approximation encloses the FRS of LTV systems. To incorporate the nonlinearities that are neglected in the derivation of the FRS of LTV systems, this work further proposes an algorithm for computing the funnel by approximating the value function of the HJB equation as a multivariate polynomial of states. From the property of the Bernstein polynomial, the conservativeness condition of the value approximation is converted as linear inequality constraints without any compromise. The proposed funnel computation algorithm consists of multiple linear programs (LPs), and thus computationally much tractable compared to most of the existing works. Finally, a constrained optimization problem is formulated to generate the reference trajectory of the system. The safety of the system is considered as nonlinear constraints of the optimization such that the funnel and unsafe regions do not intersect. Since the funnel certainly contains the FRS, the system is guaranteed to be safe regardless of disturbances. Also, the fast computation of the funnel allows the optimization problem to be solved in real-time. Consequently, the proposed method enables real-time replanning of the trajectory with safety guarantees even when the system encounters unexpected disturbances in runtime. Flight experiments of obstacle avoidance in a windy environment present the validity of the proposed planning algorithm.

로봇의 안정적인 운용을 위해서는 안전성이 보장된 경로를 계획하는 것이 중요하다. 하지만, 실제 환경에서는 예상치 못한 외란이 시스템에 영향을 주게 되므로 사전에 계획된 안전해 보이는 경로가 실제 런타임에서 안전한지 운용 전에 판단하는 것은 어렵다. 본 논문에서는 이러한 어려움을 극복하기 위한 도달 가능성 분석 기법과 이를 기반으로 안전성이 보장된 경로 계획 기법을 제안한다. 시스템의 안전 여부는 해밀턴-자코비 도달 가능성 분석을 통해 계산된 도달 가능 영역을 통해 보장될 수 있다. 실제 환경에서의 예상치 못한 외란이 시스템을 즉시 위험한 상황으로 유도할 수 있다는 점을 고려하여, 본 논문은 도달 가능성 분석의 실시간화를 목표로 한다. 본 연구에서 제안하는 도달 가능성 분석 알고리즘은 선형 시변 시스템과 비선형 시스템에 대한 두 종류의 기법들로 구성되어 있다. 선형 시변 시스템에 대한 도달 가능 영역에 대해서 본 연구는 일반화된 Hopf formula를 기반으로 하는 타원 근사를 제시한다. 해당 공식은 해밀턴-자코비-벨만 방정식의 해를 제공하기 때문에, 이를 기반으로 한 본 연구의 타원 근사는 선형 시변 시스템의 도달 가능 영역을 포함한다는 것이 보장된다. 선형 시변 시스템의 도달 가능 영역 근사 과정에서 고려되지 않은 비선형성과의 통합을 위해 본 연구는 해밀턴-자코비-벨만 방정식의 해(value function)를 다항 함수로 매개변수화하여 비선형 시스템의 도달 가능 영역을 근사화하는 알고리즘을 추가적으로 제안한다. 본 연구에서는 Bernstein 다항 함수의 특성을 활용함으로써 해당 value function의 보수성 조건이 선형 부등식 제약조건으로 변환될 수 있음을 보인다. 본 연구에서 제안하는 비선형 시스템의 도달 가능 영역에 대한 근사화 알고리즘은 복수의 선형 프로그램으로 구성되어 있으므로 기존의 도달 가능성 분석 기법들에 비해 보다 적은 계산 시간으로 도달 가능 영역을 근사화 할 수 있다. 마지막으로, 본 연구는 제안된 도달 가능성 분석 결과를 기반으로 안전성이 보장된 경로 계획에 대한 최적화 문제를 설정한다. 이 때, 시스템의 안전은 근사화된 도달 가능 영역과 안전하지 않은 영역이 겹쳐지지 않도록 하는 비선형 제약조건으로 고려된다. 본 연구에서 제안한 도달 가능 영역의 근사 결과는 실제 도달 가능 영역을 포함하기 때문에, 해당 제약조건을 만족하는 경로를 따라 운용되는 시스템은 외란에 관계없이 안전이 보장된다. 또한, 제안된 도달 가능 영역 분석 알고리즘은 실제 도달 가능 영역을 빠르게 근사화 할 수 있으므로 안전성이 보장된 경로의 실시간 최적화를 가능하게 한다. 결과적으로, 본 연구가 제안하는 도달 가능성 분석 및 경로 계획 알고리즘을 통해 런타임 중 시스템에 예상치 못한 외란이 작용되는 경우에도 시스템의 안전이 보장되도록 하는 실시간 경로 수정이 가능하다. 바람이 많이 부는 환경에 대한 드론의 장애물 회피 실험들을 통해 본 연구에서 제안한 알고리즘의 타당성 및 실시간성을 검증한다.