Offline trajectory generation

[microsoft]

Offline trajectory generation

[madratman]

hmm, for the qualifying binaries at least, you'll have enough time.
Hmm, ok, I do see some value in releasing the track early on - I don't know much about the MINLP formulation - will look into it (googling it does throw a couple of classics https://pdfs.semanticscholar.org/8533/9ee3bd042d6118ea39316a9eb4aa9eb76854.pdf, and https://www.mit.edu/people/jhow/Richards_SM.pdf).

I guess you have seen most of these anyway, but here's a paper dump for perhaps not that optimal, but real-time (grad student's interpretation of real time ofc). Might prove useful for others:

• C. Richter, A. Bry, and N. Roy, “Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,” in International Journal of Robotics Research, Springer, 2016.
• M.W. Mueller, M. Hehn, and R. D'Andrea, "A computationally efficient motion primitive for quadrocopter trajectory generation," IEEE Transactions on Robotics Volume 31, no.8, pages 1294-1310, 2015.
• Helen Oleynikova, Michael Burri, Zachary Taylor, Juan Nieto, Roland Siegwart, and Enric Galceran, “Continuous-Time Trajectory Optimization for Online UAV Replanning”. In IEEE Int. Conf. on Intelligent Robots and Systems (IROS), October 2016.
• Robust and Efficient Quadrotor Trajectory Generation for Fast Autonomous Flight, Boyu Zhou, Fei Gao, Luqi Wang, Chuhao Liu and Shaojie Shen, IEEE Robotics and Automation Letters (RA-L), 2019.
• Optimal Time Allocation for Quadrotor Trajectory Generation, Fei Gao, William Wu, Jie Pan, Boyu Zhou and Shaojie Shen, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2018, Madrid, Spain. full text
• Gradient-Based Online Safe Trajectory Generation for Quadrotor Flight in Complex Environments, Fei Gao, Yi Lin and Shaojie Shen
• Real-Time Planning with Multi-Fidelity Models for Agile Flights in Unknown Environments. Jesus Tordesillas, Brett T. Lopez, John Carter, John Ware, Jonathan P. How (ICRA) 2019

Thanks for sharing your results though, I'll try to up my game now :). We'll soon release a set of validation binaries and a corresponding validation leaderboard - which will help us gauge how easy (or how hard) the current tracks are.
If it seems people are performing really close to each other in validation and quals, it should make sense to release gate poses 2-3 days in advance of the live competition.
Hope that sounds reasonable..

[ctoumieh]

I am not using RRT*, I was just using it as an (apparently bad) example. I have developed a new method that does not rely on waypoints, but on gate sizes so that it is more optimal i.e. the constraint is that the trajectory passes through the gate and not just a point. The method will determine wich optimal point at the gate it will pass through. It indeed uses non linear optimization and gives much faster feasible trajectories (that i tested) then the polynomial method you are using. (Building_99: ~13 secs, Soccer_Field_Medium:~37 secs, Soccer_Field_Easy: ~9 secs, Mountains:~38secs) without any collision with the environment. It however requires a lot of time (that grows exponentially with the number of gates) to find said trajectory. It is basically an MINLP that is very hard to solve, let alone in real time, hence my question.
I have also designed an overtaking system that modifies the trajectory real-time when you want to overtake a drone, while avoiding collisions with the environment.
I was thinking maybe the racing maps would be released to us a day or two before the competition. If not, I guess I'll have to rely on an another planning method :).

[ctoumieh]

I was aiming for ICRA 2020 (deadline 15 Sept. i.e. in 5 days). I'll most probably publish in it, but if not it'll be IROS 2020 (deadline in Feb 2020 which will give you enough time to finish your WIP).

So I gather that (correct me if I am wrong) this may or may not be the best possible time optimal trajectory generation moveOnSpline() is capable of? Also I am assuming there is no way I can play around with ETH's code since we are getting only the binaries?

[madratman]

https://github.com/ethz-asl/mav_trajectory_generation/blob/c57ed3a7ff84ad08c4b8e3e5ddb4a3332dfe860e/mav_trajectory_generation_ros/src/time_evaluation_node.cpp

they have a benchmark script to evaluate different time allocation methods. could prove useful
For your paper, you can of course play with the ethz-asl code, as it's a standalone c++ repo.

wrt the neurips competition, I can expose time allocation parameter via a (yet another) python argument to moveOnspline, but I think that would make the competition too easy.
moveOnSpline() is meant to be a baseline / utility API people can use, if they want to focus on vision and not so much on planning.
Not making it the best possible thing (in terms of time allocation and trajectory tracking controller) should fuel the competition.

Also, yes, this may or may not be the best moveOnSpline can do in terms of time allocation and control :), and that's intentional. The best will (hopefully) be in the qualification binaries and the live competition.

[madratman]

@ctoumieh, in one of their open PRs (ethz-asl/mav_trajectory_generation#86), there's an RTD page, which also lists helpful equations for various time-alloc methods.
Might be of use.

[yannbouteiller]

Well, correct me if I am wrong, but in my understanding the gate positions will not be known before the race, so you won't be able to do this.

[ctoumieh]

I don't understand why not. I mean in the formula 1 (and the drone racing league I think - though not sure) they know well beforehand the starting position and map/gates.
I understand if for tier 2-3 this isn't allowed, but since for tier 1 the objective is time-optimal trajectory generation and adversarial tactics, and not perception/locating gates, I feel we would get more competitive/fast races if this is allowed. Otherwise some state of the art planning methods cannot be used (Teach-and-Repeat ...).

[yannbouteiller]

On the other hand, the point is generalization in my opinion. If the gate positions are known beforehand in a controlled environment, one can simply hard-code the optimal trajectory for both starting positions.

[ctoumieh]

I partially agree. First the opposing drone is not controlled so he still has to do collision/obstacle avoidance which will change said trajectory. Second, we still haven't figured out a reasonable way to get the globally time-optimal trajectory (RRT* would give you a good answer if you have infinite time) in the case of drone racing so it is still an active field of research.
Otherwise, you are 100% correct.

[ctoumieh]

I closed it by a misclick. My bad.

[madratman]

yes, in tier 1 you know the gate pose ground truth. but it will be through an API - so you can get them just at start of race.
I don't think you need an hour to generate trajectories. it's usually a few milliseconds with the right methods.
re: a global time-optimal trajectory - why do you need an RRT* in the first place? The problem is that you're given a bunch of waypoints - and your job is to fly through them as fast as you can (and as smooth as you can (and don't hit the other drone if you can as well)).
Time optimality is usually achieved by first assigning times to waypoints using a heuristic, and then obtaining a trajectory, and then optimizing for times (usually this step involves non-linear optimization))

in tier 2, yes you'll get noisy gate poses.

[ctoumieh]

I have actually read the papers you shared (except the last one). Thanks for sharing tho.
I'll start working on an alternative planning scheme then in case it doesn't work out.

[ctoumieh]

@madratman I am writing a paper detailing the method I am using and I will be using airsim (and the competition maps) as a platform to compare it with other planning methods. I have a few questions:

1. Is there anything else to cite other then the airsim paper?
2. Is your trajectory generation a fair assessment of C. Richter et al.'s method for optimal time trajectory generation capabilities? Are the rotors reaching the maximum thrust they can generate (High cost for total time in cost function)?

Also in fly_through_all_gates_at_once_with_moveOnSpline I notice you are setting v_max and a_max and passing a constant value instead of them to airsim_client.moveOnSplineAsync. Is this intentional?

Cheers,
CT

[madratman]

@ctoumieh thanks for asking!

• Yes, I've started to write a tech report for this repo, which is in a WIP stage. Can you please share the deadline of the conference you're submitting to? I'll try to get it out before then.
• Hmm, so this is slightly involved:
  Inside the moveOnSpline*() calls, I am using the non-linear optimization from ethz-asl/mav_trajectory_generation, with the following setup.

mav_trajectory_generation::NonlinearOptimizationParameters nlopt_parameters;
nlopt_parameters.algorithm = nlopt::LD_LBFGS;
nlopt_parameters.time_alloc_method = mav_trajectory_generation::NonlinearOptimizationParameters::kMellingerOuterLoop;
nlopt_parameters.print_debug_info_time_allocation = false;
mav_trajectory_generation::PolynomialOptimizationNonLinear<N> nlopt(D, nlopt_parameters);

So you, should cite the papers in their readme for sure - https://github.com/ethz-asl/mav_trajectory_generation#bibliography, and also Mellinger&Kumar

The key param in the above is the time_alloc_method, which is set to kMellingerOuterLoop.
See these lines on the respective internal time allocation methods - kRichterTime and kMellingerOuterLoop are different functions.

• if time_alloc_bound is set to kRichterTime, optimizeTime() is called, which is setting up the objective function using objectiveFunctionTime()

• if time_alloc_bound is set to kMellingerOuterLoop, optimizeTimeMellingerOuterLoop is called, which is setting up the objective function using objectiveFunctionTimeMellingerOuterLoop()

I haven't gone into the weeds of the underlying difference yet, but this should be a start. Will update after reading Richer,Bry and Mellinger, Kumar in detail again.
http://helenol.github.io/publications/iros_2015_mav.pdf talks more about ethz's work on exploiting the sparsity of the A matrix.