top of page

Online State-Time Trajectory Planning

in Highly Dynamic Crowd Environments

time1.jpg

Project Description

  • This project aims to address the navigation problem in high-dynamic environments, particularly in dense crowd scenes.

  • This project proposed a gradient-based planner over the state-time space for online trajectory generation.

  • This project porposed timed ESDT arguments that support distance and gradient queries with state-time keys to optimize motion trajectory; defined smooth prior and obstacle likelihood functions compatible with the state-time space.

  • This project valid the method with simulated and benchmark datasets.

  • More information can be found in this paper.

Project Method

Front-End Path Searching

  • State-Time Graph Building:

    • Graph Definition : Instead of searching in pixel level, we define the timed triangle graph,  a topological representation of moving obstacles. It is composed of edge and face, which depend on pedestrians' positions and velocities.​

    • Dual Graph: We discrete the time dimension into T slices with a resolution dt. We then simplify eachi triangle into  a node and build feasible connections for adjacent nodes. 

    • State-time Graph Building: We use the optimization method to execute the node-placement procedure when doing the searching.

  • State-Time A*:

    • Once the time budget T is used up or the searching process fials, the current optimal path is returned. ​

    • The neghtor retrival, i.e. SUCC is based on the graph, so the connections across diffrent time slices are built up.

    • The node placement is performed along the progress of the path searching.

BACK-END TRAJECTORY OPTIMIZATION

  • Prior Dsitribution of Smooth Trajectories:

    • To parameterize smooth trajectories, a GP prior is defined over the trajectory space, and each trajectory is sampled from this prior distribution.

    • Suppose a near-optimal time assignment t0< t1< t2 < ... < tf, is found by the front end, then the trajectory is discretized into F+1 waypoints accordingly.

  • Timed ESDF:

    • ESDF is frequently used cost map, shown in Fig2, which contains distance and gradient information against obstacles.

    • We defined the likelihood function to evaluate the clearance of the trajectory

  • MAP Trajectory:

    • Based on GP prior and likelihood function, the back-end trajectory optimization os completed by solving a MAP problem, in equation (17)​

Experimental Result

Demonstration

Statistical Analyses

bottom of page