Algorithms of solving the route movement problem are analyzed in the work. These issues are the basis for the functioning of expert systems while choosing the route under the circumstances of uncertainty. The factors that influence the motion algorithm construction by the expert system are systematized. By using ranking, it is proposed the list of factors which are the most significant in the process of the mobile rescue robot's motion algorithm construction by the expert system. The algorithm performance depends on the required accuracy of the route construction and the selection of the factors taken into account. To construct quasi-optimal solutions, it is sufficient to confine oneself to the basic (initial) algorithm. In this case, the computational costs are minimal and proportional to the number of nodes of the transport graph.
The task of finding the best possible routes according to the transportation expenses is topical for a range of technical applications, which include the following: the estimate of availability for multilocation security systems, planning of the best routes for robotic systems on the cross-country terrains, modeling of routing in simulators of mobile systems and in computer games.
The task of planning the optimal path in the general formulation is explained as follows. On the map of the area, it is necessary to determine the route of movement from the starting set of points to the set of end points, taking into account the minimum transport costs. In such a statement, the starting and ending points are not known and are determined in the calculation procedure. The following variants of tasks are possible in the partial setting: • • • to lay the optimal route from a set of starting points to a given ending point; to lay an optimal route from a set of starting points to a given set of ending points; to lay the optimal route from the given starting point to the given ending point;
2023 Copyright for this paper by its authors. • to build a transport accessibility front with a given level of costs in relation to a set of starting points.
In this case the criteria and factors, basing on which the factors of choosing the best route are chosen, are very important.
The choice of a movement route generally is the task with a high degree of uncertainty. In addition, to the task of reaching the final point of the route, a number of factors must be taken into account, which will significantly affect the options for movement in the area. In addition, the method of achieving the goal is important. To solve this problem, it is necessary to determine the necessary and sufficient factors that will influence the choice of the route. It is also important to determine their importance in the implementation of the movement towards the goal.
The object of our research is the planning of the routes of special vehicles.
The subject of the work is planning methods in the field of problems of transportation under uncertainty conditions.
The purpose of the research is to improve the process of planning and managing traffic routes in the field of transportation in uncertainty conditions by developing methods for constructing a route with the required accuracy and selecting factors that are taken into account.
The main task of the research is to determine the weight parts of the factors that form the basis for creating the expert system that will build an algorithm for the motion of mobile rescue robot.
Research methods are: the methods of solving the routing problem with minimal costs for moving taking into account the selection of factors; the methodology of adapting the algorithm of rational decisions using expert systems in uncertainty conditions for special vehicles.
The result of the study is the algorithm for planning the route of the movement of special vehicles. It takes into account the ranking of the factors forming the route by expert systems under uncertainty conditions.
Field of use: the applied spheres where there is a need for the movement of vehicles arises in conditions of uncertainty (research of unknown territories, zones of man-made and ecological disasters and accidents, military clashes).
Currently, the issue of developing mobile robotic systems with autonomous control is actual [
This paper reviews multi-robot path-planning approaches and decision-making strategies and presents the path-planning algorithms for various types of robots, including aerial, ground, and underwater robots. The multi-robot path-planning approaches have been classified as classical approaches, heuristic algorithms, bio-inspired techniques, and artificial intelligence approaches. Bioinspired techniques are the most employed approaches, and artificial intelligence approaches have gained more attention recently. The decision-making strategies mainly consist of centralized and decentralized approaches. The trend of the decision-making system is to move towards a decentralized planner. Finally, the new challenge in multi-robot path planning is proposed as fault tolerance, which is important for real-time operations.
The authors propose Robot Wireless Sensor Networks (RWSNs) management method for
maintaining wireless communication connectivity for a mobile robot teleoperation with considering a
distance between sensor nodes [
Recent studies for reducing disaster damage focus on a disaster area information gathering in underground spaces. Since information gathering activities in such post disaster underground spaces present a high risk of personal injury by secondary disasters, a lot of rescue workers were injured or killed in the past. On basis of this background, gathering information by utilizing the mobile robot is discussed in wide area. However, maintaining wireless communication infrastructures for teleoperation of a mobile rescue robot in the post-disaster underground space by various reasons.
Therefore, the authors have been discussing the wireless communication infrastructures construction method for teleoperation of the rescue robot by utilizing the RWSN. In this paper, the authors evaluated the proposed method for changing routing path by utilizing the RWSN in field operation test in order to confirm the availability of performance of communication connectivity and the throughputs between End-to-End communications via constructed network.
In graph theory, the shortest route problem can be generalized as a single-source shortest path
problem, in which the shortest route from the initial vertex of the graph and all others is found. To
solve this problem, the Dijkstra and Bellman-Ford algorithms are used, which are based on the
method of dynamic planning on weighted graphs (1956-1958) [
On the cross-country terrain the peaks of the route graph are the centers of the elementary map areas and the edges of the graph stand for transitions between the centers of the neighboring areas. The multitudes of algorithms, suggested in the following years (the algorithms of Dijkstra, Kalab, Astar etc.), in general, are the variations of the basic algorithm for fragmentary setting.
Thanks to the fact above it is possible to reach higher computation efficiency of the given algorithms if comparing to the basic algorithm. The main optimization criterion is the shortest route distance.
The methods of solving the transport problems according to the criteria of time limitation for both
static and dynamic problems can be divided into exact approaches, heuristic approaches and
metaheuristic [
The dynamic change of route’s geometric parameters is taken into account in papers [
Transportation tasks or vehicle routing tasks arise in various areas of human activity: delivery of goods from a supplier to a customer, delivery of raw materials for production, collection of industrial waste, postal delivery, etc. Since the price of transportation of various types of goods is clearly or not clearly present in their value, the reduction of transport costs is an important and urgent economic task. The goal of solving all transport problems (TP) is to draw up vehicle routes with minimal costs. TP with a time limit is a subclass of TP, they take into account the time during which the customer must be served. Being more complex in formulation, these tasks more fully describe the real process, since in many practical tasks of goods delivery, the time of arrival at the client and the time of customer service play a significant role. In transport tasks with a time limit, each customer is assigned a time period during which the customer must be served. If all customer requests are known in advance and are unchanged, the time of movement from customer to customer is known and also does not change, then such tasks are called static TP.
However, in practice, customer requests may change during the implementation of the transport
plan, the time of movement due to breakdowns or accidents also changes, so a new class of tasks,
dynamic TP with a time limit, appears. This class of tasks more fully simulates TP that occurs in
practice, and therefore allows finding a better solution compared to less adequate models [
The criteria of the best route choice are formed on the basis of the decision principle with due
consideration of factors that define the conditions of the object transportation and their condition [
Usually there are no typical factors, basing on which, one or other criteria are defined. The weight part of any given factor, while making decision regarding the route optimization or choosing the route on the terrain under conditions of uncertainty, is not defined.
A relatively new approach to finding trajectories is the ant algorithm [21].
The modification of this method consists in reducing the complexity of the traveling salesman's task, by indicating the mandatory visit of the desired nodes, it is applied to solve the task of building individual tourist routes [22].
The optimization of the ant algorithm for static maps of different sizes with typical and random distribution of obstacles is presented in the work [23], where the dependence of the path length on the population size was investigated.
The algorithm [24] provides a solution to the problem of finding the trajectory of a vehicle in real time in urban conditions with an available forecast of the road situation.
In response to the traditional WiFi location fingerprint positioning algorithm still having a low positioning accuracy, which is difficult to meet the robot indoor positioning and navigation needs, a series of improvements are made to the traditional WiFi location fingerprint positioning algorithm, so that the positioning accuracy of the algorithm can be effectively improved [25].
The experimental results show that the probability of the improved algorithm’s positioning error within 0.4 m is 49%, which is a 35% improvement over the conventional algorithm. Combining the improved positioning algorithm with our proposed grid-based navigation algorithm, the final
navigation error probability within 0.8 m is 62%.
Providing mobile robots with autonomous capabilities is advantageous [26]. It allows one to dispense with the intervention of human operators, which may prove beneficial in economic and safety terms. Autonomy requires, in most cases, the use of path planners that enable the robot to deliberate about how to move from its location at one moment to another. Looking for the most appropriate path planning algorithm according to the requirements imposed by users can be challenging, given the overwhelming number of approaches that exist in the literature.
Moreover, the past review works analyzed here cover only some of these approaches, missing important ones. For this reason, our paper aims to serve as a starting point for a clear and comprehensive overview of the research to date. It introduces a global classification of path planning algorithms, with a focus on those approaches used along with autonomous ground vehicles, but is also extendable to other robots moving on surfaces, such as autonomous boats.
Moreover, the models used to represent the environment, together with the robot mobility and dynamics, are also addressed from the perspective of path planning. Each of the path planning categories presented in the classification is disclosed and analyzed, and a discussion about their applicability is added at the end.
So, a number of factors, as well as their importance in the implementation of one or another option, are common to the implementation of navigation tasks with various options.
Based on the review and analysis of publications in the field of mobile robots, we determine the main directions of research (Figure 1).
perception
cognition
navigation The information theory The artificial intelligence
length of the route during transportation from one supplier to several consumers
terms of goods transportation from points of production to points of consumption, etc
One of the directions of mobile robot navigation is categorized into the following tasks [27]: • Generating a model of the world in the form of a map. • Computing a collision-free trajectory from a starting position to a target position. • Moving along the calculated trajectory, avoiding collision with obstacles.
The components of such tasks are: navigation skill, localization and mapping, path, trajectory, and motion planning, tracking planning, obstacle avoidance. In the article we consider the computing a collision-free trajectory from a starting position to a target position with minimization of the length of the rescue robot route.
Navigation skill. It is essential to provide enough information about the robot’s location so that it can navigate. Therefore, localization techniques are key to the navigation process. Besides, additional skills are required for mobile robot navigation.
The first of these is trajectory planning. Given a map and an objective location, it involves obtaining the trajectory that the robot must follow in order to reach the objective location. Trajectory planning is a very important issue in robotics in general, when the robot must choose what to do over the long term to attain its objectives.
The second skill is obstacle avoidance. It plays an important role in trajectory planning in order to avoid collisions.
Localization and mapping. In order for the robot to navigate successfully, it must determine its position in the workplace. So, localization together with perception and motion control are key issues in robot navigation.
Localization is closely related to representation. If an accurate GPS system could be installed on a robot, the localization problem would be solved. The robot would always know where it was. But at the moment, this system is not available or is not accurate enough to work with. In any case, localization implies not only knowing the robot’s absolute position on Earth but also its relative position with respect to a target
Path, trajectory, and motion planning. Path planning is concerned with finding the best path in order for the mobile robot to reach the target without collision, thus allowing a mobile robot to navigate through obstacles from an initial configuration to another configuration. The temporal evolution of motion is neglected. No velocities and accelerations are considered.
A more complete study, with broader objectives, is trajectory planning.
The trajectory planning entails to find out the force inputs (control ( )) to move the actuators so that the robot follows a trajectory ( ) that enables it to go from the initial configuration to the final one while avoiding obstacles. It takes into account the robot’s dynamics and physical characteristics to plan the trajectory.
In short, the temporal evolution of the motion is calculated as well as the forces needed to achieve that motion. Most of the techniques for path and trajectory planning are shared.
The task of planning the best path in general definition is formulated as follows. It is necessary to define the route from the start set of points to the set of end points on the terrain map that has minimal expenses for transportation. In such formulation the start and end points are not consciously known and are defined in the process of computation.
The following variants of the tasks are possible in partial formulation: An example of bulleted list is as following. • to map the best route from the set of starting points to the given final one; • to map the best route from the set of starting points to the given set of final points; • to map the best route from the given starting point to the given final one; • to build the front of accessibility of the final points with given level of restrictions with reference to the starting points set.
The best route is formed on the basis of criterion of the shortest distance, time, safety, saving of the luggage etc. The definition of the weight part of the factors’ influence on rescue robot’s motion algorithm formation is the basis for the expert system (ES) creation.
Start
For now, the particular technology of ES (expert system) development has been developed. It includes the following six stages: identification, conceptualization, formalization, implementation, testing and experimental use [28].
Different professionals understand the nature of the environment perception in different ways. Those of them, for whom the deductive component prevails in the academic experience, are proponents of the expert systems that are developed on the basis of artificial intelligence theory. The others prefer the systems, the knowledge base of which is formed on the empiric data. Such methodology leans on the general theory of systems and the theory of characters recognition.
The major differences between these two ideologies can be observed in the diagrams (Figure 3 and Figure 4).
The knowledge in such system are the logical rules like IF... THEN... ELSE, that are formulated by experts (in cooperation with professionals from knowledge engineering area). It means that approved decisions cannot be higher than the level of experts. The expert cannot enhance the informational abilities of the system in such organization as interactive communication between a human and a computer is based on the dialogue with already formed knowledge database (and limited by its information abilities) [29].
To define which factor is dominating in making decisions regarding the motion algorithm formation, we will use the ranking method [30]. We will select ten of the most important factors (n=10), basing on which, ES can build the algorithm of the mobile rescue robot transportation. We will also propose five experts ( = 5) to rate them.
The factors suggested for rating: • the route distance 1; • the traveling time 2; • the expenditure of energy for traveling 3; • camouflaging (visibility, noise) 4; • the conditions of traveling (obstacles, characteristics of the bearing surface) 5; • the weather conditions (the temperature, rain, snow) 6; • the probability of damage (shellfire, mine fields) 7; • the control of working capacity (minimization of overloading on the mobile robot) 8; • the commanding decisions of a human 9; • the tactical characteristics and specifications of the machine 10.
The rank matrix, received from the survey forms [29], is given in the table.
= 12 1829 = 0,89. (1)
25 (1000-10)-5 72
As the coefficient of concordance significantly differs from zero, we can consider that there is prominent connection between the opinions of researchers.
Nevertheless, researchers do not rate the factors in the same way (the received value ω significantly differs from one).
The significance of the concordance coefficient was checked according to 2 -criterion, taking into account the formula: criterion is smaller than the computing, we can claim with 95% probability that the opinion of researchers regarding the level of factors influence is matched up according to the concordance coefficient = 0,89 . It allows us to build the medium rank diagram for the given factors (Figure 5).
We can see on the diagram that the distribution is sustainable and the drop is not monotonous.
X5; 47
The rank diagram clearly shows that the expert survey made it possible to distinguish four groups of processes: the first group includes 5, 7, which we define as the main ones. The second group includes 2, 3. In the third group we can include 10, 9, 8, in the fourth group – 1, 6, 4.
In the paper [31] the methods classification is given according to the following characteristics: the context of the expert information, the type of the information received, basing on which it is possible to determine the set of methods under the conditions of uncertainty (Figure 6).
The chain of reference points (trajectory points) connecting the beginning and the end of the path is the result of such methods as: methods using a map of the environment or its description using a graph or tree; methods based on cellular decomposition; methods of potential fields; optimization methods; methods based on intelligent technologies, including behavioral methods. Then the problem of smoothing the obtained path arises.
The speed of the algorithms depends on the required accuracy of the route construction and the selection of the factors taken into account. To construct quasi-optimal solutions, it is sufficient to limit oneself to the basic (initial) algorithm. In this case, the computational costs are minimal and proportional to the number of nodes of the transport graph.
Taking into account the weight share of the factors will ensure the improvement of decisions within the optimal limit, while the computational efficiency of the integral algorithm will not be worse than the basic algorithm. Therefore, for a specific task, the use of the proposed algorithms can be significantly more effective than the use of the basic algorithm.
The models have to possess the following features: completeness, accuracy, correctness. These characteristics are connected by the notion of adequacy. The model, by using which it is possible to obtain the set goal successfully, is called adequate to this goal.
Information content
Information type
Methods sets 1. There is no need in expert information 2. Information about benefits on
criteria set 3. Information about alternatives
benefits Methods of making
decisions under conditions of uncertainty
4. Information about benefits on criteria set and
about consequences of alternatives
Qualitative (Sequence information) Quantitative evaluation of criteria benefit
Quantitative information about substitution
Doubled alternatives comparisons Lack of information about quantitative information
on consequences Qualitative information
about benefits and quantitative information about consequences Qualitative information about consequences Quantitative about substitution and
quantitative consequences
Domination PR Methods on basis of global criteria Lexicographical ordering Comparison of criteria estimates differences Method of “matching” Method “value efficiency” Methods of linear and nonlinear folding Methods of non-comparison thresholds Methods of perfect point Methods of curved indifferences Methods of values theory Quantitative evaluations Methods of mathematical programming Linear and nonlinear folding
Subject evaluations Methods of linear folding Methods of grouped ordering
Methods of highlighting the subset of objects Method of making decisions with discrete uncertainty Stochastic domination Methods of making decisions under conditions of uncertainty risk, based on global criteria Methodology of practical Methods of choosing statistical unreliable decisions Methods of curved indifferences for making decisions under conditions of risk and uncertainty Methods of decision trebles Decomposition theory methods (expected utility)
Adequacy means that the requirements of completeness, accuracy and correctness are performed not completely, but only to the extent that is enough to accomplish the set goal.
As everything in this world, models have their particular lifecycle: they emerge, develop, match or get involved into conflict with other models, then give place to the better ones. That is how the dynamics of the model reveals.
The presented algorithms cover practically significant options for laying optimal routes. The speed of the algorithms depends on the required accuracy of the route construction and the selection of the factors taken into account.
To construct quasi-optimal solutions, it is sufficient to limit oneself to the basic (initial) algorithm. In this case, the computational costs are minimal and are proportional to the number of nodes of the transport graph. Taking into account the weight share of the factors will ensure the improvement of decisions within the optimal limit, while the computational efficiency of the integral algorithm will not be worse than the basic algorithm.
Therefore, for a specific task, the use of the proposed algorithms can be significantly more effective than the use of the basic algorithm.
The use of expert systems, which include the involved ranking methods, increases the efficiency of route formation. The application of the factors ranking method provides an opportunity to apply the values of factors in the implementation the selection method of the mobile robot route in aggressive environments with a high level of uncertainty.
Such expert information system will reduce the uncertainty that is present in tasks with a low level of information. In contrast to the selection of factors, when they were used in methods randomly, here we can significantly reduce the cost of calculations with a high predictability of obtaining the best results.
Path planning tasks are one of the leading directions in the development of modern robotics.
It was proposed the algorithm for planning the route of special vehicles, which takes into account the ranking of the factors forming the route by expert systems under uncertainty conditions.
Algorithms use factors on the basis of which the minimum path is selected. These factors were systematized by the ranking method and used in the expert system.
The expert system determined their importance in conditions of uncertainty and can be the basis for creating a neural network specialized for atypical tasks in aggressive environments with a high level of uncertainty.
Using the ranking method, the list of the most significant factors for building mobile rescue robot’s motion algorithm by the expert system, has been proposed.
The ranking method makes it possible to determine the importance of factors as expert information in conditions of uncertainty for decision-making methods. It will ensure the improvement of solutions in the limit to the optimum, while the computational efficiency of the integral algorithm will not be worse than the basic algorithm.
In further research the applying of the ranking method can be used to select the importance of algorithms for the formation of the trajectory of mobile robots. The use of the algorithm is possible in the spheres of human activity, where there is a need for the movement of vehicles in conditions of uncertainty (research of unknown territories, zones of man-made and ecological disasters and accidents, military clashes).
This work was performed within the R&D "Experimental mobile robotic platform with intelligent control system and data protection" carried out by Lviv Polytechnic National University and funded from the state budget of the Ministry of Education and Science of Ukraine for 2022–2023.
[20] V. Horokhovatskyi, Analysis of alternatives vector as mean of raising the decisions adequacy in methods of structural recognition, Systems of operation, navigation and connection, 4 (2008), 45–52. [21] K. Ming. "Solving Path Planning Problem based on Ant Colony Algorithm", 29th Chinese Control and Decision Conference (CCDC), Chongqing (2017), 5391–5395. URL: https://doi.org/10.1109/CCDC.2017.7979455. [22] W. Zhang, X. Gong, G. Han, Y. Zhao. An Improved Ant Colony Algorithm for Path Planning in One Scenic Area With Many Spots, IEEE Access 5 (2017), 13260–13269. URL: https://doi.org/10.1109/ACCESS.2017.2723892. [23] R. Uriol, A. Moran. "Mobile Robot Path Planning in Complex Environments using Ant Colony Optimization Algorithm", 3rd Intern. Conf. on Control, Automation and Robotics (ICCAR), Nagoya (2017), 15–21. URL: https://doi.org/10.1109/ICCAR.2017.7942653. [24] S. Xiao. "Optimal Travel Path Planning and Real Time Forecast System based on Ant Colony Algorithm", IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conf. (IAEAC), Chongqing (2017), 2223–2226. URL: https://doi.org/10.1109/IAEAC.2017.8054413. [25] Y. Hemin, P. Jiansheng, Robot indoor positioning and navigation based on improved WiFi location fingerprint positioning algorithm hindawi. Wireless Communications and Mobile Computing (2022), 8274455: 1–13. URL: https://doi.org/10.1155/2022/8274455. [26] J.R. Sánchez-Ibáñez, C.J. Pérez-del-Pulgar, A. García-Cerezo, Path planning for autonomous mobile robots: a review, Sensors 21 (2021), 7898: 1–29. URL: https://doi.org/10.3390/s21237898. [27] F. Rubio, F. Valero, C. Llopis-Albert. A review of mobile robots: concepts, methods, theoretical framework, and applications, International Journal of Advanced Robotic Systems, March-April (2019), 1–22. URL: https://doi.org/10.1177/1729881419839596. [28] C. López, A. Ishizaka A scenario-based modeling method for controlling ECM performance,
Expert Systems with Applications 97 (2018), 253–265. [29] E.F. Mohamed, K. El-Metwally, A.R. Hanafy. “An improved tangent bug method integrated with artificial potential field for multi-robot path planning”, International symposium on innovations in intelligent systems and applications (INISTA), DOGUS University (2011), 555–559. [30] P. Ngulube Handbook of Research on Mixed Methods Research in Information Science, South
Africa, University of South Africa, 2022. URL: https://doi.org/10.4018/978-1-7998-8844-4. [31] K. Tchoń, R. Muszynski. Mathematical Methods of Automation and Robotics Wrocław, 2018.