Online Adaption of Motion Paths to Time-Varying Constraints using Homotopies

摘要

This paper presents a method for optimal point-to-point control of linear discrete-time systems with time-varying non-convex state constraints, as arising for problems of avoiding moving obstacles. While common approaches like MPC with mixed-integer programming (MIP) can quickly become time-demanding, the presented approach efficiently computes circumventing near-optimal trajectories by using homotopy properties. In a first step, a range of offline selected trajectories is used to span a region of homotopic trajectories, for which the transitioning behavior between these is determined by semi-definite programming (SDP). The online part then determines with low computational effort a collision-free and near-optimal homotopic trajectory. The procedure maps the moving obstacles for relevant collision-critical time steps into the homotopy space, and determines a suitable trajectory by a tree-search of moderate size. The circumventing trajectories and the resulting computation times are illustrated by simulation.