Algorithm for solving the Discrete-Continuous Inspection Problem

• Autorzy: Grymin R. , Bożejko W. , Chaczko Z. , Pempera J. , Wodecki M.

Identyfikatory

DOI

10.24425/acs.2020.135845

• Języki publikacji: EN

Abstrakty

EN

The article introduces an innovative approch for the inspection challenge that represents a generalization of the classical Traveling Salesman Problem. Its priciple idea is to visit continuous areas (circles) in a way, that minimizes travelled distance. In practice, the problem can be defined as an issue of scheduling unmanned aerial vehicle which has discrete-continuous nature. In order to solve this problem the use of local search algorithms is proposed.

Słowa kluczowe

EN

discrete-continuous optimization; UAV; VTOL; autonomous drone; zero emission

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2020
• Tom: Vol. 30, No. 4
• Strony: 653--666
• Opis fizyczny: Bibliogr. 19 poz., rys., tab., wzory

Twórcy

autor

Grymin R.

• Department of Control Systems and Mechatronics, Wrocław University of Science and Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Bożejko W.

• Department of Control Systems and Mechatronics, Wrocław University of Science and Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Chaczko Z.

• Faculty of Engineering and Information Technology (FEIT), University of Technology, Sydney(UTS), Australia, NSW, Sydney

autor

Pempera J.

• Department of Control Systems and Mechatronics, Wrocław University of Science and Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

autor

Wodecki M.

• Department of Telecommunications and Teleinformatics, Wrocław University of Science and Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• [1] E. H. L. Aarts and P. J. M. van Laarhoven: Simulated Annealing: A Pedestrian Review of the Theory and Some Applications, In: Devijver P. A., Kittler J. (eds), Pattern Recognition Theory and Applications, NATO ASI Series (Series F: Computer and Systems Sciences), vol. 30, Springer, Berlin, Heidelberg, 1987.
• [2] W. Bożejko, M. Uchroński, and M. Wodecki: Parallel metaheuristics for the cyclic flow shop scheduling problem, Computers & Industrial Engineering, 95 (2016), 156–163.
• [3] W. Bożejko and M. Wodecki: Solving Permutational Routing Problems by Population-Based Metaheuristics, Computers & Industrial Engineering, 57 (2009), 269–276.
• [4] W. Bożejko and M. Wodecki: Parallel Evolutionary Algorithm for the Traveling Salesman Problem, Journal of Numerical Analysis, Industrial and Applied Mathematics, 2(3-4) (2007), 129–137.
• [5] Civil Aviation Office, Report – number of valid licenses for day 31.12.2017. (2018) [online] [Accessed 1 Jul. 2019].
• [6] R. H. Byrd, P. Lu, and J. Nocedal: A limited memory algorithm for bound constrained optimization, SIAM Journal on Scientific Computing, 16(5) (1995), 1190–1208.
• [7] G. A. Croes: A method for solving traveling-salesman problems, Operations Research, 6(6) (1958), 791–812.
• [8] J. Holden and N. Goel: Fast-forwarding to a future of on-demand urban air transportation, San Francisco, CA, 2016.
• [9] F. Imeson and S. L. Smith: Multi-robot task planning and sequencing using the SAT-TSP language, IEEE International Conference on Robotics and Automation (2015), 5397–5402.
• [10] D. Kraft: A software package for sequential quadratic programming, Forschungsbericht, Deutsche Forschungs- und Versuchsanstalt fur Luft- und Raumfahrt, 1988.
• [11] N. Mathew, S. L. Smith, and S. L. Waslander: Multirobot rendez vous planning for recharging in persistent tasks, IEEE Trans. Robot., 31(1) (2015), 128–142.
• [12] J. A. Nelder, and R. Mead: A simplex method for function minimization, The Computer Journal, 7(4) (1965), 308–313.
• [13] J. Nocedal and S. Wright: Numerical optimization, Springer Science & Business Media (2006), 529–562.
• [14] M. J. D. Powell: An efficient method for finding the minimum of a function of several variables without calculating derivatives, The Computer Journal, 7(2) (1964), 155—162.
• [15] L. Snyder and M. Daskin: A random-key genetic algorithm for the generalized traveling salesman problem, European Journal of Operational Research, 17(1) (2006), 38–53.
• [16] A. Stoschek: Exploring Sense-and-Avoid Systems for Autonomous Vehicles, Vahana, [Accessed November 1, 2020].
• [17] M. Wodecki and W. Bożejko: Solving the flow shop problem by parallel simulated annealing, Lecture Notes in Computer Science No. 2328, Springer (2002), 236–247.
• [18] E. M. Wolff, U. Topcu, and R. M. Murray: Optimal control of nondeterministic systems for a computationally efficient fragment of temporal logic. IEEE Conference on Decision and Control (2013), 3197–3204.
• [19] C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal: Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Transactions on Mathematical Software (TOMS), 23(4) (1997), 550–560.

Uwagi

The paper was partially supported by the National Science Centre of Poland, grant OPUS no. 2017/25/B/ST7/02181 and statutory grant no. 0401/0023 /18 of Faculty of Electronics, Wrocław Universityof Science and Technology.