NASA Ab Initio Research: Trajectory Generation and Time Coordination in Cluttered Environments

 

Current rapidly-exploring random tree (RRT) algorithms rely on proximity query packages that often include collision checkers, tolerance verification, and distance computation algorithms for the generation of safe paths. In this video, we show the coordinated flight of two small UAS through a cluttered environment. The trajectory generation algorithm used here broadens the information available to the path-planning algorithm by incorporating silhouette information of nearby obstacles in conflict. A silhouette-informed tree (SIT) is generated through the flight-safe region of a wire maze for both UAS. The silhouette is used to extract local geometric information of nearby obstacles and provide path alternatives around these obstacles, thus focusing the search for the generation of new tree branches near these obstacles and decreasing the number of samples required to explore the narrow corridors within the wire maze. The SIT is then processed to extract a path that connects the initial location of the UAS with the goal, reduce the number of line segments in this path, if possible, and smooth the resulting path using Pythagorean Hodograph Bezier curves. To ensure that the smoothed path remains in the flight-safe region of the configuration space, a tolerance verification algorithm for Bezier curves and convex polytopes in three dimensions was developed. Lastly, temporal specifications are imposed on the smoothed path in the shape of an arbitrary speed profile with a polynomial structure.

[youtube]https://youtu.be/KMT60aIHjrg[/youtube]

Video 1:  Two Micro UAVs Fly through a Maze

[youtube]https://youtu.be/2BqdQH9BjbQ[/youtube]

Video 2: Spline Trajectory Generation with Geometric Queries – A Micro UAV Flies through a Maze

[youtube]https://youtu.be/x1aj_Tdc3I4[/youtube]

Video 3. Javier Puig Navarro Final Exit Presentation

References
  1. J. Puig-Navarro, N. Hovakimyan, N. Alexandrov, B. D Allen. Silhouette-Informed Trajectory Generation through a Wire Maze for UAS. 2018 Aviation Technology, Integration, and Operations Conference, 2018.
  2. J. Puig-Navarro, E. Xargay, R. Choe, and N. Hovakimyan. Time-critical coordination of multiple UAVs with absolute temporal constraints. In Proceedings of AIAA Guidance, Navigation and Control Conference, 2015.