Metaheuristics for Robotics. Hamouche Oulhadj
Читать онлайн книгу.
Preface
Optimization deals with methods that make it possible to optimize the use, operation and performance conditions of a system, whether it is physical or related to human activity. Situated at the crossroads of several disciplines, namely applied mathematics, computer science and artificial intelligence, optimization makes it possible to quickly find a solution to numerous problems which would otherwise be more difficult to solve relying solely on restricted mathematical analysis.
Based on heuristics or even metaheuristics at a higher level, optimization methods provide operational solutions, which are not necessarily optimal solutions but eligible suboptimal solutions, so-called acceptable solutions, because they demonstrate the level of performance required to reach a goal without conflicting with associated constraints. A number of problems whose resolution is based on optimization methods can be provided as examples:
— in finance, tax optimization is a means to minimize legal taxation;
— in databases, query optimization makes it possible to improve the accessibility of shared data, in particular by reducing transaction time;
— in telecommunications networks, routing optimization is a method for finding suitable paths for data exchange;
— in robotics, optimization allows, to take just one example, the identification of the best configurations (joint variables) that a robot must undergo in order to efficiently perform a task;
— in computer science, optimizing the code of a program makes it possible to reduce the memory space occupied and to increase the convergence time.
The applications outlined above are inherently very complex, which raises the problems of implementing accurate mathematical methods that provide admissible solutions without having to mobilize huge computational resources. In these circumstances, we are limited to considering approximated solutions, which are suboptimal solutions, but acceptable, ones since they guarantee goal realization while satisfying constraints.
In this book, we will address issues specifically related to the field of medical robotics. The focus of the applications being considered is on trajectory planning for redundant manipulative arms (articulated robots) within the context of surgical gesture assistance, and robust control for effort compensation or physical assistance in disability situations (exoskeleton). These applications are presented in detail, with the aim of understanding with the utmost clarity the problems to be solved, as well as the choices made to find effective solutions within a reasonable time frame.
The methods developed make use of optimization metaheuristics, which are high-level abstraction algorithms. Unlike heuristics, which are computational processes, often informally and “individually” adapted to specific problems, metaheuristics are general algorithms applicable to a very wide range of optimization problems, without the need to resort to a fundamental modification of the structure of these algorithms. The methods studied and results achieved are commented on and presented in detail for each of the applications addressed. Although the proposed methods are developed within the context of their application to medical robotics, their generic nature allows them to be easily expanded to other optimization problems which do not necessarily fall within the same scope of application.
Hamouche OULHADJ
Boubaker DAACHI
Riad MENASRI
November 2019
Introduction
This work is part of a collection of books, published by ISTE and Wiley, devoted to metaheuristics and their applications. Known for being specific and particular algorithms, what practical interest do metaheuristics have to make them increasingly attractive to engineers, researchers and scientists from various areas interested in different fields of application? There are two important arguments that provide us with obvious answers: on the one hand, the scope of application of metaheuristics is constantly gaining momentum, without apparently being concerned with any limitations; on the other hand, these resolution methods possess a high level of abstraction, which makes them adaptable to a wide range of engineering problems. Furthermore, a small number of necessary adjustments that do not change the nature of algorithms are usually sufficient to solve new optimization problems without any particular links existing between them.
Moreover, metaheuristics belong to a particular class of algorithms, not always easy to configure and reserved for difficult optimization problems for which there are no accurate methods to solve them more efficiently. These problems are renowned for being complex and among them we can find problems whose mathematical models are not derivable; problems whose research space is too extended to exhaustively enumerate all feasible solutions, such as problems of a combinatorial nature or involving continuous decision variables; as well as any problem making use of highly noisy, erroneous or even incomplete data, which prove unsuitable for mathematical modeling. For all these categories of problems, we generally adopt approximated solutions belonging to the field of admissible solutions, which are capable of reaching a goal without violating constraints that might be a priori imposed.
In practice, there may be several existing solutions to an optimization problem, of which only one of these solutions is generally optimal. All others are suboptimal solutions, but are still eligible, so-called acceptable, solutions because they guarantee the completion of an objective without violating associated constraints. However, the notion of optimizing acceptability may appear to be overly abstract: how can the level of solution operability be identified when the level of appreciation of that solution may vary not only from one user to another, but also with the margin of error tolerated by each type of application? Clearly, there is no absolute answer to this question, because it is ultimately each individual who decides how to define the level of acceptability for a solution, based on individual needs and the quality of the results sought for the application to be addressed.
Are metaheuristics deterministic or stochastic algorithms? Providing a clear answer to this question is also not an easy task. In effect, while it is clear that metaheuristics are not deterministic algorithms, they are also not completely stochastic algorithms. In fact, they can be categorized halfway between these two families of algorithms, because solving an optimization problem by means of a metaheuristic systematically relies on a more or less random sampling process of the solution space. When the algorithm is started, chance plays an important role in the process of finding solutions. Then, as the iterations progress, this randomness is progressively attenuated as we approach the final phase of the algorithm. Therefore, a metaheuristic will behave as a stochastic algorithm during initial iterations, and will asymptotically tend towards a greedy and deterministic algorithm during the last iterations. As we might expect, the accuracy of a metaheuristic lies in the right balance to be found between exploration phases, in which chance plays an important role, and the phases of intensification of solutions, also called phases of exploitation, in which randomness is reduced in order to focus only on potentially promising solutions. At the moment, there is no automatic parameterization method for these two search phases, whose respective weights generally depend on the type of application under study, the type of computational effort to be sustained and the type of results sought after.
Today, metaheuristics have become almost unavoidable in numerous areas of engineering due to the difficulties that have to be overcome to properly solve common optimization problems. These difficulties generally lie in the complex nature of the systems under study: the number of constraints and decision variables to be taken into account can be very high, computational times can be very long and non-differentiable objective functions can be highly multimodal or even too complex to be mathematically formalized with accuracy. The field of robotics is by nature a very broad field of application. In fact, these very relevant algorithms can be found in many applications of robotics:
—