THE DUBINS TRAVELING SALESPERSON PROBLEM WITH STOCHASTIC DYNAMICS

Motivated by applications in which a nonholonomic robotic vehicle should sequentially hit a series of waypoints in the pres-ence of stochastic drift, we formulate a new version of the Dubins vehicle traveling salesperson problem. In our approach, we first compute the minimum expected time feedback control to hit one waypoint based on the Hamilton-Jacobi-Bellman equation. Next, minimum expected times associated with the control are used to construct a traveling salesperson problem based on a waypoint hitting angle discretization. We provide numerical results illus-trating our solution and analyze how the stochastic drift affects the solution. NOMENCLATURE v Speed of Dubins vehicle ∆xi x component of distance from Dubins vehicle to way-point i ∆yi y component of distance from Dubins vehicle to way-point i θ Heading angle of Dubins vehicle u Feedback-controlled turning rate N Number of waypoints K Number of possible final heading angles θ fk Discrete final heading angle at which the Dubins vehi-cle should hit the waypoint, k = 1,...K T (·) Minimum expected time to hit the waypoint µ(n) Index in 1,...,N of the nth waypoint to be visited c(·) Edge length between two nodes ∗Address correspondence to this author