Hardware Accelerators for Unmanned Aerial Vehicles MPC algorithms

Type of position: 
Master thesis
Short abstract: 
The proposed MSc internship's objective is to design HW accelerators for UAV MPC algorithms, with the goal of improving accuracy, performance, power consumption, and silicon area.
Description: 

Robots are physical agents that interact with their physical environment. Accordingly, their sensorimotor capabilities are essential and largely determine the activities that robots can perform. In recent years, great progress has been made in sensory capabilities (especially in perception), thanks to significant advances in machine learning (ML) and dedicated ML hardware. In contrast, much less progress has been made in the area of motor skills. In the current state of the art, one of the most promising approaches is Model Predictive Control (MPC), which forms the basis of the control architecture of most advanced dynamic robots.

In MPC, the control actions are optimized over a finite time horizon, considering the time evolution of robot dynamics to optimize a given cost or reward function that describes the robot motion. 

 

From a control point of view, the following properties should be fulfilled: (1) taking into account the actual morphology when modelling the dynamics of the robot, (2) a planning horizon that is as long as possible to be able to plan complex sequences and to take contacts with the environment into account and (3) a control frequency that is as high as possible to be able to meet the real-time conditions imposed by real-world physics and, if necessary, to replan the sequence of movements.

 

Using algorithm-specific hardware acceleration, which exploits the control approach's algorithmic properties, allows the implementation of safe real-time MPC with long prediction horizons and high control frequencies. However, the structure of the control algorithms is complex, and the algorithms are sensitive to numerical errors or reduced arithmetic precision. Furthermore, failures in the control algorithms can lead to catastrophic failures and unpredictable and possibly dangerous behaviors of the robot. Thus, it is necessary to apply a Hardware-Algorithm-Co-Design approach, i.e., to adapt the currently available control algorithms to the underlying hardware and to design the hardware in such a way that it is optimally suited for the control algorithms.

 

In the last years, domain-specific hardware acceleration (using GPUs or dedicated hardware) has become increasingly popular [1], [2], [3], [4]. Since GPU acceleration suffers from high power consumption and is not flexible, a recent promising approach is to consider dedicated accelerators, such as FPGAs or Application-specific integrated circuits (ASICs) [5], [6], [7]. 

 

Similarly to GPU acceleration, FPGA designs for the computational kernels behind MPC, e.g. structured Quadratic Programming (QP) that has to be solved online and repeatedly, have been recently proposed [8]. Depending on the approach, the accelerator has to focus on various low-level linear algebra routines that compose the algorithm, such as matrix-vector multiplies, linear solvers, and matrix factorization.

 

However, designing such accelerators is a challenging task, with the resulting architectures being often so specific to a particular problem instance [7], [9], [10], [11], [12], [13], such that it is difficult to reuse them even with a related application within the same domain. Even when a general approach appears, it is usually geared for data center-level applications and does not necessarily translate easily to an embedded accelerator context. Many parallel implementations exist to accelerate MPC [14] as well as studies on accelerating MPC on FPGAs [7], [15], [16], [17]. In the very resource-constrained context of small-scale UAVs, even if FPGA platforms have been used to accelerate many aspects of UAVs, such as path planning, simultaneous localization and mapping, stereo vision, system stability, state estimation, target tracking, communications, obstacle avoidance, and interfacing with peripherals [18], MPC acceleration has not yet been demonstrated. Therefore, dedicated low-power hardware implementations are needed to push forward the limits of MPC algorithms on UAVs [19].

Envisaged Activities: 

The proposed MSc internship's objective is to design HW accelerators for UAV MPC algorithms, with the goal of improving accuracy, performance, power consumption, and silicon area. 

 

In more detail, the candidate will:

  1. Study the state-of-the-art algorithms for UAV to identify HW acceleration opportunities (e.g., parallelization, pipelining).

  2. Implement hardware accelerator(s) for the identified algorithms

  3. Integration in the UAV platform, test, and result analysis

  4. Publication of the results to an international workshop/conference

Related references: 

[1] V. Sze, Y.-H. Chen, T.-J. Yang, and J. S. Emer, “Efficient Processing of Deep Neural Networks: A Tutorial and Survey,” Proc. IEEE, vol. 105, no. 12, pp. 2295–2329, Dec. 2017, doi: 10.1109/JPROC.2017.2761740.

[2] J.-F. Zhang and Z. Zhang, “Machine Learning Hardware Design for Efficiency, Flexibility, and Scalability [Feature],” IEEE Circuits Syst. Mag., vol. 23, no. 3, pp. 35–53, 2023, doi: 10.1109/MCAS.2023.3302390.

[3] V. Mayoral-Vilches, S. M. Neuman, B. Plancher, and V. J. Reddi, “RobotCore: An Open Architecture for Hardware Acceleration in ROS 2,” in 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2022, pp. 9692–9699. doi: 10.1109/IROS47612.2022.9982082.

[4] V. Mayoral-Vilches et al., “RobotPerf: An Open-Source, Vendor-Agnostic, Benchmarking Suite for Evaluating Robotics Computing System Performance.” arXiv, Jan. 29, 2024. doi: 10.48550/arXiv.2309.09212.

[5] I. McInerney, L. Nita, Y. Nie, A. Oliveri, and E. C. Kerrigan, “Towards a Framework for Nonlinear Predictive Control using Derivative-Free Optimization⁎,” IFAC-Pap., vol. 54, no. 6, pp. 284–289, Jan. 2021, doi: 10.1016/j.ifacol.2021.08.558.

[6] A. Ravera, A. Oliveri, M. Lodi, and M. Storace, “MADS-based fast FPGA implementation of nonlinear model predictive control,” in 2023 IEEE International Symposium on Circuits and Systems (ISCAS), May 2023, pp. 1–5. doi: 10.1109/ISCAS46773.2023.10181647.

[7] I. McInerney, G. A. Constantinides, and E. C. Kerrigan, “A Survey of the Implementation of Linear Model Predictive Control on FPGAs⁎,” IFAC-Pap., vol. 51, no. 20, pp. 381–387, Jan. 2018, doi: 10.1016/j.ifacol.2018.11.063.

[8] S. Gros, M. Zanon, R. Quirynen, A. Bemporad, and M. Diehl, “From linear to nonlinear MPC: bridging the gap via the real-time iteration,” Int. J. Control, vol. 93, no. 1, pp. 62–80, Jan. 2020, doi: 10.1080/00207179.2016.1222553.

[9] M.-A. Boéchat, J. Liu, H. Peyrl, A. Zanarini, and T. Besselmann, “An architecture for solving quadratic programs with the fast gradient method on a Field Programmable Gate Array,” in 21st Mediterranean Conference on Control and Automation, Jun. 2013, pp. 1557–1562. doi: 10.1109/MED.2013.6608929.

[10] Y. Elkurdi, D. Fernández, E. Souleimanov, D. Giannacopoulos, and W. J. Gross, “FPGA architecture and implementation of sparse matrix–vector multiplication for the finite element method,” Comput. Phys. Commun., vol. 178, no. 8, pp. 558–570, Apr. 2008, doi: 10.1016/j.cpc.2007.11.014.

[11] P. Grigoraş, P. Burovskiy, W. Luk, and S. Sherwin, “Optimising Sparse Matrix Vector multiplication for large scale FEM problems on FPGA,” in 2016 26th International Conference on Field Programmable Logic and Applications (FPL), Aug. 2016, pp. 1–9. doi: 10.1109/FPL.2016.7577352.

[12] J. L. Jerez, P. J. Goulart, S. Richter, G. A. Constantinides, E. C. Kerrigan, and M. Morari, “Embedded Predictive Control on an FPGA using the Fast Gradient Method,” in 2013 European Control Conference (ECC), Jul. 2013, pp. 3614–3620. doi: 10.23919/ECC.2013.6669598.

[13] J. L. Jerez, G. A. Constantinides, and E. C. Kerrigan, “An FPGA implementation of a sparse quadratic programming solver for constrained predictive control,” in Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays, in FPGA ’11. New York, NY, USA: Association for Computing Machinery, Feb. 2011, pp. 209–218. doi: 10.1145/1950413.1950454.

[14] K. M. Abughalieh and S. G. Alawneh, “A Survey of Parallel Implementations for Model Predictive Control,” IEEE Access, vol. 7, pp. 34348–34360, 2019, doi: 10.1109/ACCESS.2019.2904240.

[15] B. Khusainov, E. C. Kerrigan, A. Suardi, and G. A. Constantinides, “Nonlinear predictive control on a heterogeneous computing platform,” IFAC-Pap., vol. 50, no. 1, pp. 11877–11882, Jul. 2017, doi: 10.1016/j.ifacol.2017.08.1413.

[16] H. I. Khajanchi, J. N. Bruno, and A. A. Adegbege, “An Embedded FPGA Architecture for Real-Time Model Predictive Control,” IFAC-Pap., vol. 53, no. 2, pp. 7833–7838, Jan. 2020, doi: 10.1016/j.ifacol.2020.12.1886.

[17] F. Xu, Z. Guo, H. Chen, D. Ji, and T. Qu, “A Custom Parallel Hardware Architecture of Nonlinear Model-Predictive Control on FPGA,” IEEE Trans. Ind. Electron., vol. 69, no. 11, pp. 11569–11579, Nov. 2022, doi: 10.1109/TIE.2021.3118427.

[18] M. Bouhali, F. Shamani, Z. E. Dahmane, A. Belaidi, and J. Nurmi, “FPGA Applications in Unmanned Aerial Vehicles - A Review,” in Applied Reconfigurable Computing, S. Wong, A. C. Beck, K. Bertels, and L. Carro, Eds., Cham: Springer International Publishing, 2017, pp. 217–228. doi: 10.1007/978-3-319-56258-2_19.

Conditions: 

The intern will be supervised by the TARAN and RAINBOW teams at the Inria centre at Rennes University, IRISA laboratory, in France. The internship remuneration will follow standard French rates.

Contact information:

For more information, contact the following people at Inria Rennes / IRISA laboratory:

Requirements: 

Good knowledge/understanding of computer architectures, hardware design, and embedded systems

Hardware Description Languages (VHDL/Verilog), Hardware synthesis flow, FPGA prototyping

Basic Programming knowledge (Python, C/C++, bash scripting)

Knowledge of Robotics algorithms is a plus

Knowledge of Design Space Exploration approaches is a plus

 

Candidates must be pursuing their MSc degree (or equivalent) in Computer Engineering, Computer Science, or Electrical Engineering.

 

Languages: proficiency in written English is required. Fluency in spoken English is also required.

 

Relational skills: the candidate will work in a research team, where regular meetings will be set

up. The candidate has to be able to present the progress of their work in a clear and detailed manner.

 

Other values appreciated: Open-mindedness, strong integration skills and team spirit.
 

Most importantly, we seek highly motivated candidates.

 

Internship start date: as soon as possible 

 

How to apply: 

Interested candidates are requested to apply via this form. The position will remain open until a satisfactory candidate is found.
In case of positive feedback, you will be contacted. If not positive, you won't hear back. 
 

Applications sent directly by email and not through the web form will not be considered!!

Supervisors : 
Dr. Marco Tognon