Abstract: Background: The most application scenario modeling of the obstacle avoidance in the path planning algorithm is based on the simplified two-dimensional grid model, so most algorithms are not suitable for the 3D space. In the real three-dimensional (3D) space path planning problem is more complicated. Firstly, the 3D map data are too big leading to complex computation. Secondly, the serial searching mode of traditional search algorithm leads low efficiency in dealing with the multitasking collaborative planning problem. Thirdly, the algorithm is easy to premature and falls into local optimal solution in dealing with a three-dimensional multitasking problem. And the proposed algorithm in this paper can well solve these problems. Materials and Methods: The real three-dimensional space model is created by the Vega Prime® in this study, overcoming the limitations of the two-dimensional model. In order to reduce the amount of operation data of the 3D environment, the map range is reduced and the path is enlarged by the points which are evenly interpolated in the path. Then change the traditional serial processing mode of the algorithm and the ant colony is divided to some subgroups and the optimal solution in each subgroup can be solved when the constraints are satisfied, then the multi-task path planning is achieved. Finally aiming at the condition of the algorithm is easy to premature, the neighborhood precise search strategy is adopted to improve the transition probabilities and walking strategies of the ant colony optimization algorithm and then the local search ability of the algorithm is improved. Results: As the simulation results shown, the search capability of the improved ant colony intelligence algorithm is enhanced, thus the success probability of path-finding is increased. Meanwhile, the convergence speed of the algorithm is improved, leading reduced time of path-planning. Furtherly, the algorithm is proved more efficient and feasible by comparative experiment with PSO, GA and APF algorithm. Conclusion: So, the multitasking path planning problem in three-dimensional virtual scenes is solved effectively. And with the multichannel-joint 3D simulation system, the effectiveness of the algorithms for three-dimensional space can be tested by the simulation without hardware conditions and reduce the cost and the risk of late hardware using.
INTRODUCTION
Domestic and foreign research mainly concentrated in the field of the single path planning and which base on the simplified grid model. The MATLAB® simulation technology is adopted to establish the two-dimensional or simplified 3D scene1-3, which does not meet the demand of the calculation of real three-dimensional space and real-time requirements. This study set up Vega Prime 2.2® (hereinafter referred to as the VP) simulation engine based on the VS.NET® and develops a three-dimension and multichannel-jointed visual simulation system for the complex scenario with many obstacles.
The efficiency of traditional serial search algorithm for single path planning problem in the two-dimensional grid map environment is low. Such as, the traditional artificial potential field algorithm is only suitable for the single path planning problem because of its serial character discussing by Alaa et al.4. Guruji et al.5 only considering the proved A* algorithm in the two-dimensional grid map built with MATLAB®, not considering the complex 3D environment. Yakoubi and Laskri6, the genetic algorithm is applied according its parallel character but also only in 2D simplified map not considering the 3D environment.
Ant colony algorithm having the parallel characteristic is chosen in this article chooses. Ant colony algorithm is the intelligent algorithm which has good robustness and less adjustable parameters. Ant colony algorithm has achieved good effect in solving large-scale optimization problem of nonlinear system, such as the service composition model established by Xia et al.7, which is constructed based on the research and improvement of the basic ant colony algorithm and can adapt the occurrence of invalid service and QoS service changes in the process of portfolio optimization service. Huang and Wu8, individuals in the group were regarded belonging to one of the pheromone diffusion source according to the principle of the closest distance to source to ensure the algorithm convergence and maintain the diversity of population in the improved ant colony algorithm and multi-objective knapsack problem is used to test the performance of the algorithm. In the ant colony algorithm selection probability rules, Meng et al.9 refered to the user demand for virtual machine resources, meanwhile the initialization of pheromone, pheromone update is improved, thus able to quickly complete the placement of the virtual machine and increase the efficiency of resources. Proper improvements of basic ant colony algorithm are given by Li et al.10. The algorithm framework is presented and the improved ant colony algorithm is used to solve the problem of logistics vehicle scheduling system, then the optimal solution is obtained. According to the optimal solution and operation criteria, the real time scheduling is realized.
But the ant colony algorithm is easy to fall into local optimal solution for solving the integer programming problems such as the task assignment on a class of discrete space and leads to convergence in advance. For three-dimensional multi-agent pathfinding problems in virtual space and to enhance the search ability of the algorithm to avoid the premature, the eight neighborhood local search strategy is adopted in the ant colony algorithm on the basis of accurate approximate iteration idea. Adjustment for the position of the local optimal points and enlarge the path points in the algorithm can effectively enhance the search ability and convergence speed of algorithm and then the three dimensional space of multitasking obstacle avoidance path planning problem is solved.
MATERIALS AND METHODS
Improvement of ant colony algorithm: With the difference of basic ant colony algorithm, the idea of precise neighborhood search is introduced to the ant colony algorithm on the basis of approximate iteration idea, which can fallback the current algorithm step and precisely search among local eight neighborhoods to choose the feasible point in a local optimum.
Spread of the pheromone: Pheromone diffusion is the key to the ant colony for finding the optimal path. Pheromone updating rule is that after the ants moving step between two paths points, pheromone concentration on the path will be increased. New pheromone is produced as the standard of the best path and map pheromones are updated after completion of the movement of all the ants. To prevent falling into local solution rapidly11, the pheromone volatilization factor is adopted, so the pheromone updating formulas are as Eq. 1 and 2:
| (1) |
| (2) |
where, ρ is volatile factor, Δτij(t) is the amount of pheromone left by K ants on the path.
0Improved moving strategy: With the accurate search idea in the classical search algorithm, assume that a single ant exists in a 3×3 squares world of the ant colony algorithm, so the ant has eight points to choose (Fig. 1).
| Fig. 1: | Eight neighborhood search |
| Fig. 2(a-b): | Local optimum trap |
The probability that each point is selected is proportional to its pheromones and is inversely proportional to the distance to the end point. Therefore, each point selected transition probability is in Eq. 3:
| (3) |
The elements in the allowedk are the collections of the next path points for the k-th ant to choose. Information stimulating factor α indicates the importance of the pheromone. Expect stimulating factor β represents the importance of heuristic information in route choice. Inspiration function ηje(t) is the distance between the current point and end point12 as in Eq. 4:
| (4) |
where, dje represents the distance between the current point and the target.
Eight points are used for roulette selection and the total probability is:
A number p which is between 0 and total is generated randomly and pi1 to pi8 are used to compare with p in turn, if p<pij, then the point j corresponding with pij is the next point for ants to reach. The ants move along with the rules, until the next moving point is the end point.
When the transition probability of the single ant is calculated and the roulette selection algorithm is accomplished, the next point is get and the next point P2 is belong for the obstacle area, then the ant will stop moving such as Fig. 2a. After the 8 neighborhood precise search is introduced, ants can be back to the history position P1 and continue searching the obstacle point P3, then the original path point P2 are deleted to avoid the trap of the optimal solution in the region of the obstacle as shown in Fig. 2b.
Improved ant colony algorithm: The improved ant colony algorithm steps are as follows:
| Step 1: | Initialize maps, pheromone information |
| Step 2: | Empty the path information of the ant objects |
| Step 3: | The transition probability for each ant object is calculated and the next position of each ant object is obtained by roulette selection algorithm. And the next position is deleted if it is not possible and the last position is returned to search the feasible solution within the eight neighborhoods. If the ants research the finish point, the number of ants which have completed search adds 1 and if all the ants arrived at the end point, turn to step 4 |
| Step 4: | Calculate and save the optimal solution of all the ants object and then turn to step 5 |
| Step 5: | Update the environment pheromone. If the iteration is completed, the optimal path is expanded by the interpolation, otherwise turn step 2 |
The algorithm has two main improvements:
| • | In step 3, if the next path position of a single ant is found to be unreasonable, namely into local optimal solution, when updating the new position, the position will be back to the history optimal position of the ants by the improved algorithm and the eight neighborhood search is adopted in the history optimal position and the ant will walk to the feasible and closest location to the end point |
| • | The delete operator is introduced. In step 3, for optimizing the path of each ant, the delete operator is introduced to remove the detours. When the route number is less, the turn point is more less and certain error is brought when the ant through the turning point each time. So reduce the turning point can reduce the error. At the same time, according to the principle of the distance between two points, one of the biggest turning angle route or bend angle of the minimum route is removed |
Multitasking path planning based on improved ant colony algorithm: Method can be used to reduce the problem size to avoid precocity and so the population can be decomposed to multiple sub groups. Meanwhile, a suitable expression method is seeked to make the subgroups corresponding with the feasible solution, which is the key for the algorithm application to multitask path planning13.
Multi-task allocation: For the problem of multi agents and multi-tasking planning, the key of multi-tasking problem is to determine which target should be assigned to the corresponding agent. Thus the individuals in intelligent algorithm can be divided into multiple subgroups and the U-dimension space is constructed to correspond with the task allocations for U agent-subgroups, thus the U-dimension vector is designed for each agent subgroup, where xi is set as the serial number of target position for the sub-agent to arrive. For example, six agents will arrive at three targets respectively and then the target position vector x of the subgroups is shown in Table 1.
From Table 1, subgroup 1, 3 collaboratively arrive at target 1 and subgroup 2, 4 cooperatively arrive at target 2 and subgroup 5, 6 arrive at target 3 cooperatively.
Steps of multi-tasking planning which is achieved by intelligent algorithm based on the division of subgroups are as follows:
Step 1: Initialization:
| • | The whole group is divided into some overlapping subgroups |
| • | Each dimension of target position vector X within each subgroup is randomly selected from integer 1-T numbers 1-T (target numbers) represent the serial number of the target |
| • | Initialize the speed and position of each individual in subgroup |
| • | All objective function values of individuals are evaluated and the initial individual position is set as the optimal solution of individual |
| Table 1: | Target position vector of each subgroup |
Step 2: Repeat the following steps until the destination is found or the iterations number exceeds maximum:
| • | The transition probabilities are calculated for each individual to select the next position(X, Y). When (X, Y) exceeds its scope, the next position equals to the boundary |
| • | Compare the fitness function value of each individual with its history best value and then update the optimal value |
| • | Find the nearly optimal solutions in each subgroup and the approximate optimal solution of the total swarming |
Based on the above subgroup algorithm, the targets and tasks of each agent are decomposed for each subgroup in the system and the targets and tasks are assigned to different levels, thus the reasonable hierarchical planning tasks are accomplished as shown in Table 1.
Multitasking path planning constraints: The constraint conditions14 of path planning problem not only consider a single mission requirements of the object, such as the maximum turning angle and at the same time the coordination and cooperation relationship between the various objects also need to be considered, such as the minimum safety distance constraints.
Maximum turning angle: It limits the generated trajectory can only be less than or equal to the predetermined maximum turning Angle range and walking task. The constraints depend on the performance of the object and walking task. The distance between the points is ai = (xi-xi-1, yi-yi-1) and maximum allowable bend angle is φ and the biggest corner angle constraint can be represented as in Eq. 5:
| (5) |
where, the |a| is the length of the vector.
The no-collision constraints between objects, that is when inspection path trajectory pi, considering other track pj. The minimum distance between objects walking along the pi and other objects is db as shown in Eq. 6:
| (6) |
where, ds is the minimum safe walking distance between object.
3D multitasking path planning simulation design based on improved ant colony algorithm: The 3D map and barrier model are loaded by using Vega Prime 2.2® and the corresponding channel, observer, the object are established, then the collision detection function between the object and 3D terrain is implemented by isector collision class. The VP environment is built in the MFC and the ACF file of VP® is called15, then the related message response is implemented and the list of obstacle coordinates for the scene terrain is calculated. Vega Prime2.2® thread is created by calling the AfxBeginThread function in main thread class CWinApp of MFC applications and the VP worker thread is started, then the VP visual window is refreshed with the frame cycle in the background.
Channel design of path planning simulation system: The instance of entity object class is new constructed, whose position and orientation properties are set and its parent-child relationships with the scene is also set. New observer and a parent-child relationship with the scene are set and then subsidiary relationship with the environment is set up. New channels and corresponding observers are selected in the observer options. New transform class instance and the parent-child relationship are set respectively with the object class16.
Steps of adding the main visual channel are as follows:
| • | Define the primary visual channel (hereinafter referred to as "main channel") and set its position in the window, then the window and graphics are associated |
| • | Define the primary observer and associate the channel with observer |
| • | Change observer position according to control in the frame loop and realize real-time car movement binding in main channel |
The multi-task path planning software system in 3D real-time complex scene is designed and OpenGL interface is used to draw the projection of the 3D planned path in the overlook channel on the left of system interface, then the global movement of virtual objects in the whole scene can be observed in the overlooking channels on the left interface. On the right of the system interface, the virtual objects are real-time binded in the six main channels respectively and each observer location bindings in the end of each virtual object. And each car movement and obstacle avoidance can be real-time observed from the back of the car, meanwhile the car current location information are real-time updated real-time in each top left position of channel. Channel names are marked as "1", "2", "3", "4", "5", "main".
Design of interface for ant colony algorithm with the VP program: Interaction process of three-dimensional ant colony intelligence pathfinding algorithm with the VP-MFC program is as follow: Through the button on MFC-VP program17 interface to select and then the targets are distributed to each subgroup and each subgroup in the ant colony algorithm can respectively obtain the sub-target location. At the same time, the algorithm obtains the obstacle coordinates to build the corresponding map matrix and calculates the pathfinding path, then return the path coordinates list to the MFC-VP program. According to the path coordinates, MFC-VP program achieves multi-task allocation for each car and the real-time path planning for each sub target.
The parameters for ant colony algorithm provided by the VP program:
| • | Size of map (length, width and height), start and end coordinates are defined in ant colony algorithm parameters. Obstacle coordinates parameters are stored in List <point>, which is defined as ListPoint lBarrier |
| • | Obstacle avoidance path for the VP program returned by ant colony algorithm |
After the success of the obstacle avoidance pathfinding, each subgroup plans the path line in the list <point> list respectively and the list is returned to the VP program and then the program plans the path on the overlooking channel according to path point coordinates in the returned path list llPath, at the same time various car pathfinding obstacle avoidance information are real-time displayed on the main visual channels.
Further optimization of the algorithm in three-dimensional space: Due to the map in 3D virtual space range is 1×1×1 km and large scope will lead the search speed of ant colony algorithm too slow, not suitable for real-time 3D scene. Therefore, the map is reduced to 100×100×100 m in the ant colony algorithm, then enlarge the path point number to 10 magnification by using interpolation method in two adjacent points evenly to the 10 points.
RESULTS
Simulation experiments: Three dimension virtual scene space of simulation system is 1×1×1 km and ant number of algorithm is set to 20, meanwhile iterative times are set to 200, α = 1.0 , β = 2.0.
To better observe the overall situation of multi-task planning in global overlooking channel, a OpenGL interface is added in the original program to render the path real-time in the overlooking channel (the GlPointSize function can set the size of the drawing point and the GlVertex2f function can draw path points in the window's client area and glColor3f function can set the drawing color). The paths planned by subgroup 1 are drawn with the blue line and the paths planned by subgroup 2 are drawn with the yellow line and the path planned by subgroup 3 are drawn by green line.
Algorithm results and simulation analysis in different situation: Click on the menu "multi-path planning" and sub menu-"parameter setting" after program running and the dialog box is get as in Fig. 3. The dialog box is divided into three parts: the setting part of target location and the setting part of vehicle start time interval and the task allocation setting part. The target location settings are divided into three types: the preferred goal setting, regular goal setting and general goal setting. Select the target 1 as the preferred target, the target 2 as a regular goal and goal 3 as a general target. That is the six objects are allocated with three target locations. And the car 1, 2 are allocated to goal 1 (315,672), car 3, 4 are allocated to goal 2 (788,675) and car 5, 6 are allocated to goal 3 (236,298).
As shown in Fig. 3, the three dimensional space pathfinding algorithm based on the basic ant colony algorithm cause the failure of pathfinding.
After the accomplishment of the target assignment and adoption of the improved ant colony algorithm, click the "ok" button, then the first object start planning path and a path is real-time drawn in the looking down channel on the right side of the simulation system, then the rest of the objects have arrived in the assigned target location as shown in Fig. 4. Car 1 and 2 of subgroup 1 plan the blue path, car 3 and 4 of subgroup 2 plan the yellow path and car 5 and 6 of subgroup 3 plan the green path planning.
Figure 4 shows that the improved algorithm can avoid obstacles and reach the target location effectively, meanwhile it solves the multitask path planning problem and the effectiveness of the algorithm is proved.
| Fig. 3: | Failure of path planning with unimproved particles algorithm |
| Fig. 4(a-b): | Starting position is different with time interval for 3 sec, (a) The whole path planning in 3D virtual scene and (b) Enlarge figure for the overlooking channel |
| Fig. 5(a-b): | Starting position is different with time interval for 0 sec, (a) The whole path planning in 3D virtual scene and (b) Enlarge figure for the overlooking channel |
Set time interval to 0 and again goal 1 (700, 400) to subgroup 1, goal 2 (300, 298) to the subgroup 2 and goal 3 (560, 475) to the subgroup 3. And the simulation results are shown in Fig. 5.
Start the car for multi-task planning as shown in the Fig. 6, where without collision between each car and satisfying the multitasking pathfinding collision constraint conditions.
Click on the screen by the mouse and then the car starting position is determined, namely the cars are on the same starting point. Assign the target location (320, 671) to subgroup 1, target location (648, 475) to the subgroup 2 and goal 3 (780, 670) to subgroup 3. Each subgroup plans the path as shown in Fig. 6.
| Fig. 6(a-b): | Starting position is different with time interval for 2 sec, (a) The whole path planning in 3D virtual scene and (b) Enlarge figure for the overlooking channel |
In Fig. 6, when the end point and the starting point are located in the dense regions of obstacles, the improved algorithm can still avoid obstacle and plan the path (as shown in yellow path) successfully, which prove the robustness of the algorithm.
The improved and or not algorithms are tested many times with the same terrain scene, the same starting point and end point and some of these results are shown in Table 2. Record the time it takes to find the path in Table 2 (unit: second), I f the pathfinding fail, to remember as "-".
In Table 2, the improved algorithm obviously enhances the success probability of pathfinding and shorter the pathfinding time, which show that the improved algorithm’s search ability and convergence speed is greatly improved.
| Fig. 7(a-b): | Multitasking path planning result with particle swarm optimization algorithm, (a) The whole path planning in 3D virtual scene and (b) Enlarge figure for the overlooking channel |
| Table 2: | Pathfinding case statistics with the algorithm before and after improvement |
Analyzing the results of simulation and particle swarm optimization algorithm: The Particle Swarm Optimization (PSO) algorithm, genetic algorithm and artificial potential field algorithm are achieved in 3D simulation system, which plan the paths in each subgroup, using the same beginning and end point as shown in Fig. 4 in which the improved ant colony algorithm is used and the simulation results are shown in Fig. 7-9, respectively.
Contrast the Fig. 7 and 4, the fact as follows can be seen: (1) Planning path by particle swarm algorithm is easy to fall into local optimal solution as shown in the green line, two groups 5, 6 particles trapped in local optimal solution and unable to bypass obstacles to reach goals.
| Fig. 8: | Multitasking path planning result with genetic algorithm |
| Fig. 9: | Multitasking path planning result with artificial potential field algorithm |
By the improved ant colony algorithm is proposed in this study, each subgroup is solvable and can bypass obstacles to reach target correctly and more effective. (2) The path planned by Particle Swarm Optimization (PSO) is more rectangular line and is close to the current obstacles but the proposed algorithm considering the corner of the vehicle, which is more practical. Contrast the Fig. 8 and 4, the search strategy of genetic algorithm is based on the solution space and as same as ant colony algorithm, genetic algorithm also considers solution of the problem in the global view but the path planned by genetic algorithm is not optimal compared with the path planned by ant colony algorithm in Fig. 4. Contrast the Fig. 9 and 4, search strategy of the artificial potential field algorithm is based on the local search, resulting in the local optimal solution and then one green path is terminated, meanwhile the yellow paths planned by artificial potential field algorithm span across the obstacles, which are inadvisable.
DISCUSSION
So far, for the problem that the scenario for traditional path planning simulation is set up by the simplified grid model using MATLAB® simulation technology, which does not meet the computing needs of real three-dimensional space and the real-time and interactive of simulation18,3, the multi-channel combined three-dimensional visual simulation system for path planning is achieved whose three-dimensional visual simulation engine with the interface for intelligent algorithms is constructed successfully based on vs net using multi-threading technology. Domestic and foreign research mainly concentrated in the field of the single path planning19,20, the study of the multi-task collaborative planning for multi-objective in complex scenes is not see more. Serval algorithm can be adopted in the multi-task collaborative planning, such as artificial potential field, Genetic Algorithm (GA), Particle Swarm Optimization (PSO) algorithm. The artificial potential field algorithm is simple and easy to implement but it is easy trapped into the local solution when it is in the multi-planning in complex and multi-obstacle environment21. And in this study, the implementation of artificial potential field algorithm for multi-task collaborative planning is achieved and is contrasted with the ant colony optimization algorithm. The simulation results show that the plans planned by the artificial potential field algorithm treat the obstacle position as a local optimal solution, thus through the obstacles and be infeasible, meanwhile, these planned plans of artificial potential field algorithm are more rectangular polylines, clingy and bypass the current obstacles to get goals. Particle algorithm of particle swarm algorithm for the path planning problem only achieved good effect in a single task and no validation in the mission planning of the implementation effect is achieved22. And the PSO algorithm is achieved in multi-task collaborative planning in this study and is proved to failure planning contrasted with the ant colony algorithm. Randomness for genetic algorithm is stronger and it is suitable for the local search and dynamic programming23, then the implementation of GA for multi-task collaborative planning is achieved and is proved less effectiveness with the ant colony optimization algorithm in this study. And the ant colony algorithm is essentially parallel, which can search within the multi-points at the same time and its results are often very ideal. Under the condition of hardware to allow, the optimal solution can be get by ant colony algorithm and this is the reason that despite its complex, it is widely used. Meanwhile, its reliability is high.
CONCLUSION AND FUTURE RECOMMENDATIONS
In this study, the improved ant colony algorithm is used in three dimension visual simulation system and effective obstacle avoidance of multitasking coordinated path planning simulation system is efficiently implemented where are 23 obstacles in large map under complex scene and solved the three-dimensional complex multitasking path planning problem in virtual scene and furtherly compared with Particle Swarm Optimization (PSO) algorithm, then the simulation results further proved that the improved ant colony algorithm applied to the three dimensional space is more effective and feasible.
ACKNOWLEDGMENT
Financial support was provided by S and T research fund of Hubei provincial Department of Education (B2015226).