Timed Trajectories for Multi-UAVs

Question

Timed Trajectories for Multi-UAVs

Opened this issue 6 years ago · 1 comments

It took me a while to understand, but I realize my approach was wrong

Because even in Blender by itself, I'm finding it hard (very hard) to plan the paths in a timed manner. (maybe due to my lack of experience with Blender)

I suppose the current concept is: (Please correct me if I'm wrong)

What is a Trajectory:
Given a sequence of Waypoints (coordinates) that a drone needs to go, what's the smoothest way (high order polynomial) to get to them, while meeting UAV physical limits.
Current commit also assumes velocity of zero at the initial and final Waypoint of the Trajectory.

Between each waypoint is a 7th order polynomial, expressing X, Y, X and Yaw
A Trajectory is a set of 7th order polynomials with a duration of how long each polynomial should be executed. (A Trajectory is a piecewise polynomial)
The sum of each polynomial duration is the total duration of the Trajectory

With multiple UAVs, we have the concept of "Formations".
A set of UAVs with their respective initial Waypoint is the initial Formation. Vice versa, the final Waypoint is the final Formation in a set of UAVs

How fast a drone transforms from a Formation to another can be adjusted using the Timescale of the Trajectory.
If it is desired for all drones to arrive their final Waypoint at the same time, Timescale for each drone may need to be adjusted accordingly.

We need a more granular Timescale

Currently there is no fine control over timing, only the duration of a whole Trajectory using Timescale.
(I'm still not really sure how timescale works, seems like it's related to poly4d_stretchtime() in crazyflie firmware)

Good control on timing is useful for collision avoidance

A whole Trajectory can be sped up or slowed down to reduce chances of a collision (however that will affect the arrival time to the final Waypoint

These are the ways I have thought of to gain granular control over Timescale:

Split a Trajectory into two Subtrajctories. Slow down the first Subtrajectory, and then speed up the other Subtrajectory. This way we can avoid a collision, while being able to arrive to the final Waypoint at desired time
But in this repo, the drone will stop between Subtrajectories as velocities are assumed to be zero at final and initial Waypoint
(we need to fully stop a drone, instead of smoothly slowing down and speeding up)
To fix this, we may need a velocity vector for initial and final waypoint (not just magnitude).
A separate timescale for each polynomial, instead of a global one which we have now.
From what I understood in source code, this can easily be achieved, and should have rather good results. This way we can slowdown a polynomial and speed up another, to achieve the same total Trajectory duration
An advanced method is to introduce a Timescale polynomial, this way, we can smoothly adjust how fast or slow certain parts of a Trajectory should be.
(I'm really not sure how the math can be done)

That away we'll have nearly full control over the motion, especially in the case of multiple UAVs,

TODO:

I'm going to implement num 2 and submit a PR(timescale for each polynomial), as the maths seems to already be implemented, just needs to change the way the Timescale variable is used

Even though it's not recommended to use num 1, it may still be useful to be able to set a velocity vector for initial and final waypoints.

For num 3 (Timescale polynomial), after your suggestions / tips, I may try to implement this given that it's a good approach

Also, there already is a duration variable in the output of this repo, wouldn't it make sense to optimize/solve the duration of each polynomial, to be able to arrive each waypoint at a the desired time? Then it can potentially generate timed trajectories for collision-free points generated from libMultiRobotPlanning

Answer 1 · 2019-05-09T22:41:18.000Z

This seems like the correct understanding to me overall. What you are trying to solve is known as the multi-robot motion planning problem. You can find one of my papers related to that topic here: http://act.usc.edu/publications/Hoenig_TRO2018.pdf.