Keywords

1 Introduction

Multi-Objective problem means that solving a problem needs to consider multiple objectives, and the objectives are conflicting and restricting each other. Generally speaking, optimizing one of the objectives will lead to the weakening of other objectives. For example, in the path planning problem, it may be necessary to consider multiple objectives such as the quantity of blocked paths, path length, and the quantity of intersections. There may be exist where the length of path is short but the quantity of blocked paths or the quantity of intersections is relatively large. Therefore, there may be more than one optimal solution for the Multi-objective optimization problem (MOP) [1,2,3,4,5], and there may be a set composed of multiple optimal solutions. The front composed of these optimal solutions in the objective space are called Pareto Front (PF). In MOP, there may be two or more global or local Pareto optimal sets, some of which may correspond to the same PF, which is the Multi-modal Multi-objective Optimization Problem (MMOP) [6].

MMOP can be described as

$$ min_x^{f\left( x \right)} = min_x^{\left[ {f_1 \left( x \right),f_2 \left( x \right), \ldots f_m \left( x \right)} \right]} ,x \in {\Omega },f_i \left( x \right) \in R^m $$
(1)
$$ PS = \left\{ {PS_1 , \ldots PS_k } \right\}, k > 1 $$
(2)

where the decision vector \(X = \left( {x_1 ,x_2 , \ldots x_n } \right)\) belongs to the non-empty decision space Ω, the objective function vector \(f:{\Omega } \to {\Lambda }\) consists of \(m\left( {m \ge 2} \right)\) objectives and \({\Lambda }\) is the objective space. A few relevant definitions are briefly described below: a solution \(x \in {\Omega }\) in a decision space that satisfies these constraints is called a feasible solution. Given two solutions \(x,y \in {\Omega }\) and their corresponding objective vectors \(f\left( x \right),f\left( y \right) \in R^m\), \(x\) dominates \(y\) (denoted as \(x \prec y\)) when \(\forall i \in \left\{ {1,2, \ldots ,m} \right\},f_i \left( x \right) \le f_i \left( y \right) \) and \(\exists j \in \left\{ {1,2, \ldots ,m} \right\} , f_j \left( x \right) < f_j \left( y \right)\). A solution that is not dominated by any other solution is defined as Pareto optimal solution. In Eq. (2), it is assumed that \(PS_k\) is the k-th Pareto optimal solution, \(\left\{ {PS_1 \ldots PS_k } \right\}\) denotes multiple equivalent Pareto optimal solutions, corresponding to the same PF, PS is a set consisting of \(PS_k\).

In this paper, a new path planning combinatorial algorithm is proposed to solve the MMOPP problem. Firstly, to improve the speed of the global path search of ACO, Dijkstra is used to improve the initial pheromone concentration allocation for different costs and increase the accuracy of the initial search. Secondly, in order to maintain the diversity of solutions in the decision space, non-dominated solutions are retained in the ant colony algorithm by judging dominant relationships. Finally, in order to maintain the diversity of the objective space and avoid getting stuck in the local optimal solution, the pheromone threshold is set.

2 Related Works

2.1 MMOPP Example

The path problem is a typical MOP problem. As shown in Fig. 1, from the start point to the end point, there are three optimal paths. These three paths correspond to the same path length and the same congestion point. The optimal solutions of these paths correspond to the same PF in the objective space. The purpose of this study is to obtain multiple paths with optimal and equal target values, such as the length of multiple paths, the number of blocked road sections, and the number of cross-road conditions.

Fig. 1.
figure 1

Three paths corresponding to the same point in PF

Full size image

2.2 Research on MMOPP Problems

From the perspective of practical application, the research of MMOPP problem is usually divided into three types. One is path planning that simulates real-life road conditions [6], decision makers need to consider planning requirements such as path length, congestion points, and must-pass points at the same time. Two is the vehicle path planning considering the logistics distribution requirements [7], which usually needs to consider the load constraints of the distribution vehicles and the time constraints of the distribution points. Another is to consider robot path planning [8], which needs to consider planning requirements such as path length and obstacles. This paper considers the first MMOPP problem, and studies the Multi-objective Path Planning problem under the requirement of multi-modal optimization.

From the point of view of selection algorithm, classical path planning algorithms such as Dijkstra algorithm and A* algorithm only consider the optimization of path length, which is hard to resolve the MMOPP problem. Genetic algorithm [9], particle swarm algorithm [10], evolutionary algorithm NSGA-II [11], etc. can also solve the MMOPP problem, but these algorithms focus more on approaching the PF, ignoring the diversity of solution distributions in the decision space. Therefore, most scholars choose to introduce swarm intelligence algorithms with self-organization, self-adaptation and self-learning characteristics to realize MMOPP. The ACO used in this paper is used by many scholars to solve the path problem. People are committed to improving ACO to improve its effectiveness and applicability. At present, it mainly focuses on two aspects: process improvement and parameter setting. In terms of process improvement, Mao [12] proposed an improved A* algorithm to quickly find a better path, and adjust the pheromone concentration on the path through coefficients. MOHAMED et al. [13] proposed a solution method combining local search and ACO to solve the vehicle routing problem with loading capacity constraints. In terms of parameter setting, Yuan et al. [14] studied the path problem of the tea picking robot, improved the ant colony algorithm, and improved the global search ability and computational efficiency by changing the adaptive adjustment pheromone concentration value and iterative termination conditions. Liu et al. [15] proposed adaptive pheromone concentration and dynamic pheromone volatilization factor when designing a path navigation system for indoor service robots. The improved ACO has higher global search ability.

The MD-ACO used in this paper combines the process improvement and parameter setting to solve the MMOPP problem. The MMOPP test set used in the algorithm validation phase includes numerical quantification of targets such as path length, road width, road congestion, and blocked road segments, and includes solution constraints for the must-pass point problem. Therefore, the test experiments in this paper have a tightly coupled relationship with the actual application scenarios. The experimental results verify that the MD-ACO can solve the multi-modal and multi-objective path planning requirements in parallel. The comparison with other algorithms shows that the algorithm proposed in this paper has stronger search ability and optimization ability, and the diversity of solutions is better.

3 Problem Description

In this chapter, we describe the MMOPP problem based on the documentation provided by the test set [16,17,18]. This test set models the road features in the actual road network map into a regular grid map, which is divided into three categories according to the types of optimization objectives, with a total of 12 test questions. The first type of test problem simulates the congested road sections in the actual road network map, and its optimization goal is to minimize the path length, the quantity of congested road sections, and the quantity of intersections. According to the size of the problem, this type of problem contains 5 test questions. In the second type of test problem, different F values are used to simulate information such as road congestion or road width, and the optimization objective is to minimize the path length and each F value. According to the number of optimization objectives, this type of problem contains 5 tests question. The third type of test problem simulates the path planning requirements that have must-pass points constraints, and allows the existence of a re-entrant path. The optimization goal is to minimize the path length and each F value. According to the different scale of the problem, this type of problem contains two test problems.

The test set provides some definitions. The map is a two-dimensional matrix consisting of 0 or 1. The matrix value of 0 means that this area is passable in the map, and the value of 1 means that this area is not passable. Walking in four directions is permitted, repeating the same path is not allowed, and it is forbidden to go beyond the boundary of the map. As shown in Fig. 1, the map also gives the starting point and ending point, red congestion points, yellow must-pass points. At the same time, passing a certain area in the map will generate different costs, this cost has multiple dimensions, including road width, road congestion, the number of intersections, and must-pass points.

The cost of each area is expressed as (3), the cost of the path is expressed as (4).

$$ cost \to \left[ {f_1 ,f_2 , \ldots f_m } \right], f_m \in F $$
(3)
$$ cost_{path} \left[ i \right] = \mathop \sum \nolimits_{j = 1}^n cost\left[ j \right]\left[ i \right],i \in M $$
(4)

In formula (3), the cost array consists of the costs of different optimization objectives. In formula (4), \(cost_{path} \left[ i \right]\) is defined as the i-th cost sum of this path, \(cost\left[ j \right]\left[ i \right]\) is defined as the i-th cost of the j-th region on this path (Fig. 2).

Fig. 2.
figure 2

Map example

Full size image

4 Proposed Approach

4.1 Matrix Pre-processing

Since the test set provides us with a 0–1 matrix, we need to preprocess the matrix at first. The optimization of matrix preprocessing also helps to reduce the scale and complexity of the problem. Matrix preprocessing includes three steps. First, we need to get rid of useless roads, it means to turn some 1 in the matrix that are considered as useless areas into 0 in a 0–1 matrix. The result obtained at this time is still a 0–1 matrix. Second, we need to get the set of valid points, it means that we need to get a set of some key points in the matrix, then check the feasibility of the problem. Third, we need to turn the 0–1 matrix into a weighted directed graph.

Removal of Unless Areas.

We can process the 0–1 matrix and delete unnecessary areas in the map to shrink the problem scale. Abridged regions can be divided into two types. First, disconnected regions belonging to two road segments are useless. Second, we get all the key points from the map. If the must pass point is not in this group of areas separated by key points, we can ignore this group. The following Fig. 3(a) is the original map generated by the two-dimensional matrix, and the following Fig. 3(b) is the reduced map after matrix preprocessing.

Fig. 3.
figure 3

Comparison of original and reduced maps

Full size image

I will then describe the algorithms and algorithm-related auxiliary arrays used to implement this section. Depth[x][y] represents the depth of DFS search. Minor[x][y] represents depth of the nearest common ancestor in DFS search. Children[x][y] represents the subset of children of area (x, y) in DFS search. Must[x][y] represents whether the current point is a necessary point.

After creating the auxiliary matrix, we can build a DFS spanning tree by first traversing the map, and then traversing the DFS spanning tree to do the following operations. If the child node \(\left( {x^{\prime},y^{\prime}} \right)\) of \(\left( {x,y} \right)\) belongs to children[x][y], and \(minor\left[ {x^{\prime}} \right]\left[ {y^{\prime}} \right] \ge depth\left[ x \right]\left[ y \right]\) and \(\left( {x^{\prime},y^{\prime}} \right)\) is not a necessary point, then the subtree rooted at \(\left( {x^{\prime},y^{\prime}} \right)\) can be deleted.

figure a

Get Key Points and Check Problem Feasibility.

We first traverse the retained points obtained in the previous step, and then select the start point, end point, must-pass point, and intersection point among the retained points to form a key point array. In addition, before starting to solve the MMOPP problem, we need to check whether the problem has a feasible solution. For some scenarios with necessary points, we need to check whether all feasible solutions have passed the necessary points. This verification is achieved by traversing all retained points and determining whether all necessary points are included.

Build a Weighted Directed Graph.

We first traverse the key point set obtained in the previous step, calculate all the costs between the key points, and construct a weighted directed graph, where the weights refer to different types of costs. The data structure of the edge includes the starting point, the ending point, the cost array of the edge, the path composed of all points, and the unique identifier id of the edge. The data structure of the edge is as follows (Fig. 4).

Fig. 4.
figure 4

The data structure of the edge

Full size image
figure b

4.2 Initial Pheromone Assignment Based on Dijkstra Algorithm

ACO is designed to simulate the action mode of ant colony looking for food. Ant colonies secrete different pheromones along the way when searching for food, and the amount of pheromone is related to the distance of the path. Other ants will make corresponding decisions according to the concentration of pheromone on the path, and finally the ant colony will gradually gather on the shortest path. Since the initial pheromone concentration of the traditional ACO is evenly distributed, the initial search of the algorithm has strong blindness, which leads to a slow convergence speed and easily makes the algorithm get stuck in local optimum and affects the optimization ability of the algorithm. In order to avoid the algorithm getting stuck in local optimum due to pheromone and reduce the misleading of ants caused by wrong heuristic information, improve the path planning ability of the algorithm, this paper improves the allocation of initial pheromone based on the minimum cost planned by Dijkstra algorithm.

The Dijkstra algorithm is a classic algorithm for finding the shortest path. Since this paper studies multiple objectives, the objectives to be optimized are not only related to the path length, but also related to different types of cost. The algorithm steps are as follows. First, for each type of cost, we use Dijkstra algorithm to traverse the map, then we can obtain the minimum cost path and the minimum cost sum from the start point to the end point. Second, the pheromone of the point on the least-cost path is set according to formula (5). π is a constant, \(cost_i\) represents the total cost of the i-th cost on the minimum cost path, The pheromone of points on a non-minimum-cost path is set to \(\mu_i\) according to formula (6). Finally, the pheromone of each different cost is accumulated as the initial pheromone allocation.

$$ pheromone\left[ i \right] = \frac{\pi }{cost_i } , i \in costType $$
(5)
$$ \mu_i = pheromone\left[ i \right] - \theta $$
(6)
figure c

4.3 Select the Next Node According to the State Transition Rules

In the process of ants walking, the ants will select the next point to reach according to the probability rule, and record the next point that the ants walk through in the taboo table. The probability of choosing the next path is expressed as the formula (7).

$$ P_{ij}^k \left( t \right) = \left\{ {\begin{array}{*{20}l} {\frac{{\left[ {\pi_{ij} \left( t \right)} \right]^\alpha *\left[ {\varphi_{ij} \left( t \right)} \right]^\beta }}{{\sum_{s\epsilon allowed_k } \left[ {\pi_{is} \left( t \right)} \right]^\alpha *\left[ {\varphi_{is} \left( t \right)} \right]^\beta }}} \hfill & {j\epsilon allowed_k } \hfill \\ 0 \hfill & {other} \hfill \\ \end{array} } \right. $$
(7)
$$ \varphi_{ij} = \frac{1}{{cost_{ij} }} $$
(8)

where \(P_{ij}^k \left( t \right)\) represents the state transfer probability of ants k from point i to point j at time t. \(\pi_{ij} \left( t \right)\) denotes the pheromone concentration on the path from point i to point j.

In the process of ant walking, if it reaches the end point and has passed all the necessary points, and if the current solution is dominated by the solutions in the PS, it will not be added to the PS. If the current solution is not dominated by the solutions in the PS, it will join the PS.

4.4 Update Pheromone

After all ants have completed a traversal, the residual information on the paths is updated and the pheromones on each path are adjusted according to the following formula.

$$ \pi_{ij} \left( {t + 1} \right) = \pi_{ij} \left( t \right)*\left( {1 - \rho } \right) + \Delta \pi_{ij} \left( t \right), 0 < \rho < 1 $$
(9)
$$ subject\;to\; a \le \pi_{ij} \left( {t + 1} \right) \le b $$
$$ \Delta \pi_{ij} \left( t \right) = \mathop \sum \nolimits_{k = 1}^m \Delta \pi_{ij}^k \left( t \right) $$
(10)
$$ \Delta \pi_{ij}^k = \left\{ {\begin{array}{*{20}c} {\frac{Q}{cost_k }} \\ 0 \\ \end{array} } \right. $$
(11)

In formula (9), \(\rho\) denotes the pheromone volatility coefficient, \(\Delta \pi_{ij} \left( t \right)\) denotes pheromone increment on path \(\left( {i,j} \right)\) after this cycle, if \(\pi_{ij} \left( {t + 1} \right) \) exceeded a threshold, we take the threshold as its value. In formula (10), \(\Delta \pi_{ij}^k \left( t \right)\) denotes the pheromone content left on the path (i, j) by the kth ant in this cycle. In formula (11), if ant k passes through \(\left( {i,j} \right)\) in this cycle, then execute \(\Delta \pi_{ij}^k = \frac{Q}{cost_k }\). \(cost_k\) represents the total cost of all paths taken by ant k. Q is the total amount of pheromones released by ant k after completing a complete path search.

5 Experimental Results

All algorithms are implemented in C++ language and compiled on CLion. The test set of the experiment, the Pareto Set and the Pareto Front obtained by running the algorithm are as Table 1.

The evaluation criteria of the experimental results are as follows. The point in the PF is assigned 1, and N found paths corresponding to the point which actually existed M paths is regarded as an additional (N − 1)/M score. As shown in the Fig. 5, the winner’s score is \(2 \times 1 + \frac{4 - 1}{6} + \frac{3 - 1}{6} = 2.8\). While the loser’s score is \(3 \times 1 + \frac{1 - 1}{6} + \frac{2 - 1}{6} + \frac{2 - 1}{6} = 3.3\). Compared with other algorithms, MD-ACO algorithm scores are as Table 2.

Table 1. Problem scale and results
Full size table
Table 2. The score of the problem1–12
Full size table

From the above experimental results, it can be concluded that the evaluation score of the MD-ACO algorithm is higher than other algorithms. Especially for problem 5, problem 9 and problem 10, MD-ACO algorithms can find more solutions than other algorithms.

Fig. 5.
figure 5

An example of calculating fractions

Full size image

6 Conclusions

The main research content of this paper is to solve the MMOPP problems through the MD-ACO. First, matrix preprocessing is performed to process the initial data. Second, Dijkstra is used to optimize the initial pheromone distribution of the ACO. Finally, the ACO is used to traverse the map. The experiment proves the feasibility and effectiveness of the MD-ACO algorithm to solve the MMOPP problems.