Open AccessArticle

Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with Crevasses

Seokjin Kang

¹ and

Heoncheol Lee

^1,2,*

School of Electronic Engineering, Kumoh National Institute of Technology, Gumi 39177, Republic of Korea

Department of IT Convergence Engineering, Kumoh National Institute of Technology, Gumi 39177, Republic of Korea

Author to whom correspondence should be addressed.

Symmetry 2024, 16(9), 1229; https://doi.org/10.3390/sym16091229

Submission received: 3 August 2024 / Revised: 10 September 2024 / Accepted: 14 September 2024 / Published: 19 September 2024

(This article belongs to the Special Issue Symmetry/Asymmetry in Operations Research)

Download

Browse Figures

Figure 1
Flowchart of the proposed method. "> Figure 2
An example of calculating altitude distance between nodes a and b. "> Figure 3
The visualization of the concept of the probabilistic modeling of crevasses. The z-axis represents the probability of the existence of crevasses around the measured crevasses points. "> Figure 4
A part of the Google map of the Antarctic environments with the virtually measured positions of crevasses represented by red areas. "> Figure 5
The graphical results of the probabilistic modeling of crevasses. The areas with crevasses are probabilistically represented. The areas with higher values represented by lighter colors describe more probable areas with crevasses. "> Figure 6
Experimental results of the proposed method, ACO, and GA in the Antarctic environment with 20 nodes. The proposed method produced more efficient task scheduling results with shorter total paths than the other algorithms. (a) The proposed method, (b) ACO, and (c) GA. "> Figure 7
Experimental results of the proposed method, ACO, and GA in the Antarctic environment with 30 nodes. The proposed method produced more efficient task scheduling results with shorter total paths than the other algorithms. (a) Proposed method, (b) ACO, (c) GA. "> Figure 8
Experimental results of the proposed method, ACO, and GA in the Antarctic environment with 40 nodes. The proposed method produced more efficient task scheduling results with shorter total paths than the other algorithms. (a) The proposed method, (b) ACO, and (c) GA. ">

Versions Notes

Abstract

This paper deals with the problem of multi-robot task scheduling in the Antarctic environments with crevasses. Because the crevasses may cause hazardous situations when robots are operated in the Antarctic environments, robot navigation should be planned to safely avoid the positions of crevasses. However, the positions of the crevasses may be inaccurately measured due to the lack of sensor performance, the asymmetry of sensor data, and the possibility of crevasses drifting irregularly as time passes. To overcome these uncertain and asymmetric problems, this paper proposes a probabilistic multi-robot task scheduling method based on the Nearest Neighbors Test (NNT) algorithm and the probabilistic modeling of the positions of crevasses. The proposed method was tested with a Google map of the Antarctic environments and showed a better performance than the Ant Colony Optimization (ACO) algorithm and the Genetic Algorithm (GA) in the context of total cost and computational time.

Keywords:

multi-robot task scheduling; Antarctic environments; probabilistic crevasse modeling

1. Introduction

As robotics technology advances, robots have become capable of replacing humans in many fields. Robots can take over tasks that are dangerous, time-consuming, or require precise work, among others. One advantage of robots is their ability to operate in environments that are challenging for humans. An example of such an environment is Antarctica, which is characterized by extremely low temperatures, vast ice-covered terrain, crevasses between glaciers, and strong winds, making it difficult for humans to access directly. Antarctica holds significant economic and scientific value, making exploration of the region highly important. Robots are being used to explore Antarctica in place of humans.

A typical multi-robot system consists of multiple robots working together simultaneously to accomplish tasks. While each robot operates independently, they communicate and collaborate to achieve the overall goal. The key advantage of a multi-robot system is the ability to divide tasks, thereby reducing time and maximizing efficiency through cooperation between robots. This is particularly beneficial when exploring large areas or performing complex tasks, as multiple robots can operate simultaneously to optimize performance. However, in extreme environments, multi-robot systems must adapt to specific conditions such as extremely low temperatures, strong winds, and limited energy resources. Therefore, robots in such environments require enhanced autonomy and durability, as well as energy-efficient designs.

For efficient exploration, proper utilization of robots is necessary; however, exploring a vast terrain like Antarctica with a single robot takes considerable time. Therefore, the use of multiple robots is being actively researched, as this approach allows for simultaneous exploration of larger areas. However, it requires advanced technology for control systems and computation, including research in areas such as coverage, task allocation, and scheduling for multiple robots.

The primary goal of scheduling is to optimize the tasks of robots and reduce travel time. When multiple robots need to reach target destinations, it is essential to allocate the destinations appropriately to minimize each robot’s travel distance. This can be seen as a variation of the Traveling Salesman Problem (TSP). TSP involves visiting a set of destinations exactly once and returning to the starting point while minimizing the total travel distance [1,2,3,4]. Various algorithms exist to solve the TSP problem, among which the Nearest Neighbors Test (NNT) algorithm calculates the shortest path by visiting the nearest destination first, offering simplicity and fast computation [5].

Among heuristic algorithms, Ant Colony Optimization (ACO) is an algorithm inspired by the behavior of ants searching for food and returning to their nests [6,7]. ACO has been applied to both symmetric and asymmetric TSP problems, and a cooperative learning approach has been proposed [8,9]. The ACO algorithm has continued to evolve and is now widely used in various optimization problems [10,11]. Recent research has further enhanced the performance of ACO in solving TSP problems by optimizing its parameters, and a study utilizing the Taguchi method to optimize ACO parameters has also been conducted [12]. Another heuristic algorithm is the Genetic Algorithm (GA), which mimics biological evolution. Since its initial introduction, GA has been improved to handle large-scale problems effectively [13,14,15]. Additionally, the theoretical foundations of GA have been established, enabling its use in search and optimization fields [16]. The problem of multiple robots visiting destinations is known as the Multiple Traveling Salesman Problem (MTSP), which applies when multiple robots need to visit different destinations [17,18,19]. In environments such as Antarctica, MTSP is considered suitable for exploring vast areas, and the process of returning to the starting point after visiting all destinations is excluded [20,21,22,23]. Scheduling in Antarctica differs significantly from typical environments due to the presence of ice-covered terrain, steep slopes, crevasses, and strong winds. Crevasses can change in location and size over time [24,25]. To address this, a probabilistic model using a Gaussian distribution is applied to crevasse data [26], considering the variability in crevasse positions and sizes. Previous studies have proposed methods to minimize steep slopes while visiting destinations, but they were limited in fully reflecting the Antarctic environment [27,28]. Therefore, this study improves scheduling by integrating crevasse data with the elevation information used in previous research to find safer routes. However, crevasse positions may be inaccurately measured due to limitations in sensor performance and data asymmetry, and crevasses may drift irregularly over time. To overcome these uncertainties and asymmetries, this paper proposes a multi-robot task scheduling method that combines the NNT algorithm with probabilistic modeling of crevasse positions.

The structure of this paper is as follows: Section 2 discusses the definition of MTSP, and the challenges faced in the Antarctic environment when applying MTSP. Section 3 describes the proposed multi-robot task scheduling method based on the NNT and the probabilistic modeling of the positions of crevasses. Section 4 compares the experimental results with other algorithms. Section 5 presents the conclusion, summarizing the information discussed.

2. Problem Description

This paper addresses the issue of multi-robot scheduling in the Antarctic environment. It explores the challenges posed by the icy and snowy conditions and hazardous terrain unique to Antarctica. To overcome these challenges, the paper defines a multi-robot scheduling approach tailored to this environment.

2.1. Antarctic Environments

Antarctica is one of the coldest regions on Earth, with temperatures never exceeding 0 °C and an average annual temperature of −23 °C. Covering an area of approximately 13,660,000 square kilometers, it is the fifth-largest continent after Asia, Africa, North America, and South America. About 98% of it is covered in ice, and these extreme conditions make the operation of exploration robots very challenging. Crevasses, which are cracks in the glacier surface, and steep slopes on icy paths are major hazards that must be avoided in the robots’ travel routes. The method proposed in this paper extends the existing Multiple Traveling Salesman Problem (MTSP) to suit the Antarctic environment, considering the unique situation where robots share the same starting point but do not return to it after visiting all nodes. The innovative approach of this study focuses on calculating optimal paths that avoid crevasses and steep slopes by reflecting the unique topographical features of the Antarctic continent. To achieve this, a newly developed weighted cost function, which combines crevasse avoidance and slope analysis, enables stable scheduling and path planning for robots in the extreme Antarctic environment. This approach contributes to maximizing the operational efficiency of Antarctic exploration robots while ensuring safety.

2.2. Multi-Robot Scheduling Problem

The multi-robot scheduling problem is defined as the task of visiting all designated nodes. In this paper, it is described as a single depot problem, where all robots start from the same location, must visit at least one node, and do not return to the starting point. The problem involves each robot r visiting a set of nodes

H = \{h_{1}, h_{2}, h_{3} \dots, h_{N_{1}}\}

where

n = 1,2, \dots, N_{1}

in the shortest possible route. Each robot visits nodes according to the number of visits

S = \{s_{1}, s_{2}, s_{3}, \dots, s_{r}\}, (r = 1,2, 3, \dots, R) .

Each robot has a travel sequence

P_{r}

, defined as follows:

P_{r} {= \{{\overset{ˇ}{h}}_{n}^{r}\}}_{n = 1, \dots, s_{R}} w h e r e {\overset{ˇ}{h}}_{n}^{r} \in H

(1)

Here,

{\overset{ˇ}{h}}_{n}^{r}

represents the set of nodes visited by robot r, and

s_{r}

is the number of nodes visited by robot r. This is expressed as:

\sum_{r = 1}^{R} s_{r} = N_{1}

(2)

The total travel distance

D i s t (P_{r})

for each travel sequence

P_{r}

, with the distance between node

{\overset{ˇ}{h}}_{n}^{r}

and

{\overset{ˇ}{h}}_{n + 1}^{r}

being

d_{n}^{r}

, is calculated as follows:

D i s t (P_{r}) = \sum_{n = 1}^{s_{r} - 1} d_{n}^{r}

(3)

The objective is to find the minimum total travel distance

P_{r, m i n}

, defined as follows:

P_{r, m i n} = {a r g m i n}_{P_{r}} (D i s t (P_{r}))

(4)

Ultimately, the goal is to determine the set

P_{m i n}

, which minimizes the total travel distance for all robots. This can be expressed as:

P_{m i n} = {P_{1, m i n}, P_{2, m i n}, P_{3, m i n}, \dots, P_{R, m i n}}

(5)

To minimize the travel distance, the number of nodes

s_{r}

each robot r visits must be set, and an appropriate algorithm must be used to find

P_{m i n}

2.3. The Issues of Crevasse Avoidance

Crevasses [29] are open fractures or fissures on the surface of glaciers formed due to localized strain exceeding the ice’s tensile strength. These cracks can be just a few millimeters wide but may extend hundreds of meters in length and depth. Over time, glacier movement can alter the position and shape of these crevasses, posing significant hazards to exploration robots. Narrow and deep crevasses are particularly difficult to detect, increasing the risk of robots falling in, leading to potential damage or mission failure. Therefore, avoiding crevasses is crucial for safe and successful robotic exploration. Robots must use sophisticated sensors and algorithms to detect crevasses in real time and navigate safely. This technology ensures that exploration missions in harsh polar environments can continue, contributing to polar research and climate monitoring. Thus, crevasse avoidance is a vital element in robotic exploration, essential for enhancing both the survival and success rates of missions.

3. Proposed Method

In this chapter, we provide a detailed explanation of the proposed method for optimizing the path of multiple robots in the Antarctic environment. The proposed method aims to efficiently plan the movement paths of robots by considering the unique terrain features of Antarctica and the risks posed by crevasses. To achieve this, we introduce a new cost function that integrates altitude information and crevasse data based on the Nearest Neighbors Algorithm. This chapter first presents an overview of the proposed method, followed by an in-depth discussion of its key components, including the probabilistic cost function and the multi-robot scheduling algorithm.

3.1. Overview

Figure 1 is the overall flowchart of the proposed method. The proposed method is based on the Nearest Neighbors algorithm, which searches for the most suitable route through exhaustive investigation. The proposed method adapts the NNT algorithm by incorporating altitude information and crevasse data to define a new cost function, considering the Antarctic environment. The crevasse information, modeled probabilistically, allows for safer route scheduling. This paper presents a new cost function that considers the unique conditions of Antarctica.

3.2. Probabilistic Cost Function with the Probabilistic Modeling of Crevasses

In this paper, crevasses are modeled arbitrarily. In the actual Antarctic environment, crevasse observations may be inaccurate, and their locations might change after being observed. Recognizing the difficulty in accurately reflecting real conditions, a new cost function incorporating probabilistically modeled crevasse areas is defined. Firstly, in our previous work [28], the concept of the altitude distance to approximate altitude distance to account for three-dimensional distances was used for the realistic cost function to reflect the Antarctic environmental property. An example of calculating the altitude distance is shown in Figure 2.

To calculate the altitude distance between node a and b, the distance

d_{a b}

is sampled

N_{2}

times, and the value d is defined as

d_{a b}

divided by

N_{2}

. The altitude values sampled between nodes a and b,

E_{a b}

, are expressed as:

E_{a b} = (e_{1}, e_{2}, \dots, e_{N_{2} - 1}, e_{N_{2}})

(6)

where

e_{n}

represents the height at the n sampled point (where

n = 1,2, \dots, N_{2}

). The difference in altitude values

h_{n}

, is given by:

h_{n} = e_{n + 1} - e_{n}

(7)

The altitude distance D_ab between nodes a and b, reflecting the altitude values, is calculated as:

D_{a b} = \sum_{n = 1}^{N_{2} - 1} \sqrt{d^{2} {+ h_{n}}^{2}}

(8)

The angle value

f_{n}

between

e_{n}

and

e_{n + 1}

, which are parallel to the x-axis, defines the factor

f_{n}

between node a and b as:

F_{a b} = \sum_{n = 1}^{N_{2} - 1} f_{n}

(9)

In the Antarctic environment, accurate path planning is essential to ensure that robots can approach or safely avoid crevasses during exploration. However, the positions of crevasses may change over time, and due to the limitations of sensors, their locations may not be accurately measured. Therefore, using a Gaussian distribution to probabilistically model the surrounding risks based on the center points of crevasses helps the robots plan optimal paths to avoid crevasses even in uncertain environments. Additionally, to better reflect the actual Antarctic environment, the crevasse areas between nodes a and b were probabilistically modeled using a Gaussian distribution. Figure 3 describes the concept of the probabilistic modeling of crevasses in a 200 × 200 pixel space in the simulation environment.

The measured crevasse points indicate the locations with the highest probability of crevasse occurrence, representing the centers of the crevasses. These central points are areas with the greatest risk of crevasse formation compared to the surrounding regions, making them crucial information for actual exploration or safety planning. The risk around these central points is modeled using a Gaussian distribution, which shows that the probability of crevasse occurrence decreases with distance. Areas closer to the center have a higher likelihood of crevasse presence and are visually represented in white. As the distance from the center increases, this probability decreases, transitioning to red, with areas without crevasses shown in black. This type of probabilistic modeling quantifies the uncertainty in crevasse occurrence, allowing the robots to optimize their paths to avoid crevasses during exploration. Additionally, the standard deviation σ determines the variability in crevasse occurrence probability, serving as a key factor in controlling the width and spread of the risk area around the crevasse. The probabilistic modeling value

g_{a b} (p, q)

for the crevasse area using a Gaussian distribution is as follows:

g_{a b} (p, q) = {\frac{1}{2 π σ^{2}} e}^{- (p^{2} + q^{2}) / 2 σ^{2}}

(10)

where p and q are the distances from the center of the kernel in the coordinate system, and

σ

is the standard deviation of the distribution. The total probability between nodes a and b is given by:

G_{a b} = \sum_{k = 1}^{M} g_{a b} (x - x_{k}, y - y_{k})

(11)

Here,

G_{a b}

is the Gaussian distribution value at the observation point, and the observation points are

(x_{k}, y_{k})

. x and y are the coordinates of the specific point being measured, and M represents the number of crevasse observation points. The final proposed cost function is:

{c o s t}_{a b} = c_{1} D_{a b} + c_{2} F_{a b} + c_{3} G_{a b}

(12)

where

c_{1}

c_{2}

, and

c_{3}

are the weights of each component and can be set arbitrarily depending on the situation. More precisely, the weights can be adjusted according to the optimization priorities set by the user. For example, if safety is the top priority, the weight c3, which reflects the crevasse risk (

G_{a b}

), can be set higher. Conversely, if the efficiency of the travel route is more important, the weight c1, which reflects the altitude distance (

D_{a b}

), can be set higher. These weights can be flexibly adjusted depending on the given environment or objectives, allowing for the planning of an optimal route tailored to various situations. For instance, in areas where crevasses frequently occur, setting a higher c3 can enhance safety, whereas in relatively flat areas, increasing c1 can help select a more efficient route.

D_{a b}

represents the altitude distance between node a and b,

F_{a b}

represents the altitude value between node a and b, and

G_{a b}

reflects the crevasse risk, with the Gaussian distribution normalizing all probability values between 0 and 1 to express the relative risk and uncertainty of crevasses.

3.3. Multi-Robot Scheduling Method with the Probabilistic Cost Function

The proposed multi-robot scheduling method is based on the probabilistic cost function described in the previous section and the NNT (Nearest Neighbors Test) algorithm as its backbone. The NNT algorithm is an efficient method that repeatedly selects the node with the lowest cost to determine the path. This approach is particularly advantageous in scenarios where real-time pathfinding or resource constraints are critical due to its low computational cost. While other backbone methods exist, such as the ACO (Ant Colony Optimization) algorithm [6,7,8,9,10,11,12] and GA (Genetic Algorithm) [13,14,15,16], these often involve high computational costs and complexity. Therefore, the NNT was chosen as the backbone for the proposed method.

The key aspect of this algorithm is its integration of probabilistically modeled crevasse information into the cost function, helping multiple robots find the optimal path while avoiding crevasses. The crevasse risk cost evaluates the potential risk encountered when moving from one node to the next, enabling the robots to choose the safest path.

The pseudo-code of the proposed method is shown in Algorithm 1. This algorithm takes the number of robots and a list of nodes to visit as input and outputs the optimal path for each robot. Specifically, in each search iteration, the robot calculates the distance cost required to move from the current node to other candidate nodes. Then, it calculates the crevasse risk cost, which assesses the expected crevasse risk on the path based on probabilistic modeling.

Algorithm 1. Multi-robot Scheduling Algorithm in Antarctic Environments with Crevasses.

Input Number of robots R and nodes to visit N
Output The final multi-robot’s tour T

1: Initialize the multi-robot’s tour T.
2: Divide nodes among robots by using fair division.
3: for r

\leftarrow

R do
4: Initialize each robot’s tour t and remove visited nodes.
5: While there are nodes left for the robot to visit:
6: For each unvisited node n:
7: Calculate the total cost based on distance, altitude, and crevasse risk.
8: Select the node with the minimum total cost.
9: Update each robot’s tour t and mark the selected node as visited.
10: End for
11: Append each robot’s tour t to the final multi-robot’s tour T.
12: Return the final multi-robot’s tour T.

These two cost components are combined to yield the total cost, and the robot selects the next node with the lowest total cost as its next destination. This process repeats until all nodes have been visited. As a result, the proposed method enables robots to choose the safest and most efficient paths, considering the presence of uncertain crevasses.

Additionally, it is beneficial to provide examples of how this algorithm can be applied under different environmental conditions. For instance, when exploring areas with a high concentration of crevasses, the weight of the crevasse risk cost can be increased to find a path that minimizes risk. Conversely, in relatively flat areas with fewer crevasses, the weight of the distance cost can be increased to select a shorter, more efficient route.

This approach significantly contributes to increasing the survival probability of robots and improving mission success rates in extreme environments, such as Antarctic exploration.

4. Results

This chapter explains the results obtained by applying the proposed method. To verify the effectiveness of the proposed method for optimizing multi-robot paths in the Antarctic environment, experiments were conducted in the actual Antarctic environment. This chapter discusses the experimental results in the Antarctic environment and provides an analysis based on these results.

Results in the Antarctic Environment

To apply the proposed method in the real Antarctic environment, a location was set at 74° 37.4′ S, 164° 13.7′ E using Google Maps. Using Google Earth, the distance and altitude data for the paths that the multi-robot system will traverse were obtained. Google Earth provides 3D maps of various terrains, allowing the extraction of three-dimensional data, including altitude changes along the routes. These data are utilized to plan the robot’s paths more accurately and to avoid terrain obstacles such as crevasses. The altitude values for each path were sampled 500 times at equal intervals. Figure 4 shows an image of the Antarctic environment, including crevasses, extracted from Google Maps. The red areas in Figure 4 indicate the crevasse regions. Figure 4 is an image with dimensions of 4704 × 3968 pixels, representing an actual environment of 35 km × 25 km. The size of one pixel is 7.44 m/pixel in the horizontal direction and 6.30 m/pixel in the vertical direction. Figure 5 shows the results of probabilistic modeling using a Gaussian distribution based on the crevasse regions shown in Figure 4. Probabilistic modeling, which is a mathematical method that includes uncertainty and variability in systems or phenomena, was used to model the crevasses probabilistically to minimize issues arising from the uncertainty in crevasse observations.

To compare the proposed method, the ACO and GA were applied in the same environment. The parameters for each algorithm are as follows: the cost function weights are set to

c_{1}

= 5,

c_{2}

= 1,

c_{3}

= 1. The parameters for ACO are a ants = 40, iteration = 50, α = 2, β = b, φ = 0.1, ρ = 0.05,

z_{0}

= 0.5. The parameters for GA include a mutation rate = 0.05, population = 50, generation = 300, with selection operator as the tournament, crossover operator as two-point, and elitism applied. The following Figure 6, Figure 7 and Figure 8 present the comparative experimental results of the proposed method, ACO, and GA according to the number of nodes. In the figure, red dots and blue dots represent the starting point and the nodes to visit, respectively. The red curve-shaped areas represent crevasse regions, and the straight lines with different colors represent the paths of different robots. As shown in the figures, all the methods were successfully conducted and found their best scheduled multiple routes while avoiding the measured positions of crevasses.

To quantitatively evaluate the performance of the proposed method, the altitude distances and runtimes according to the number of nodes were calculated and compared with ACO and GA, as shown in Table 1 and Table 2, respectively. The comparison results showed that the proposed method had shorter altitude distances and runtimes in all cases, indicating that it is more efficient in terms of energy and time compared to the other methods. Table 1 shows the comparison of altitude distances for each method. Altitude distance represents the amount of elevation that changes a robot’s experience while moving, and smaller values indicate lower energy consumption and more efficient paths. The proposed method demonstrated superior performance in generating energy-efficient routes with shorter altitude distances across all node counts compared to ACO and GA. Table 2 presents the comparison of runtimes for each method. Runtime refers to the time required by the algorithm to find the optimal path, with smaller values indicating faster computation. The proposed method showed significantly shorter runtimes in all cases compared to ACO and GA, demonstrating its ability to compute the optimal path more quickly.

5. Conclusions

This paper proposed a probabilistic method for multi-robot task scheduling in Antarctic environments with crevasses. The proposed method uses an improved cost function that integrates altitude information and crevasse data, with the NNT algorithm as its backbone, to generate stable and efficient routes. Specifically, this method ensures that robots can operate safely and stably even in the harsh conditions of Antarctica by finding routes that avoid crevasses. As a result, the proposed method demonstrated the ability to generate shorter paths in a shorter time compared to ACO (Ant Colony Optimization) and GA (Genetic Algorithm), enabling efficient and reliable task scheduling. These results validate the effectiveness of the proposed method in addressing the major challenges that robots face in extreme environments like Antarctica. The proposed method can be applied to various real-world applications in the Antarctic environment. For example, it can be used to optimize the paths of robots during Antarctic exploration, allowing them to avoid crevasses. This method also aids exploration robots in effectively analyzing the diverse terrain features of Antarctica and selecting safe routes. Future research will consider additional environmental factors in Antarctica to enhance the practical applicability of the proposed method. For instance, the method’s utility will be further strengthened by incorporating extreme weather conditions, real-time data updates, and various terrain obstacles. Additionally, the potential application of the proposed method to other polar regions or terrains with similar hazards will be explored. This will help establish a foundation for the widespread use of this method in robotic operations in extreme environments.

Author Contributions

S.K.: methodology, software, validation, and writing—original draft preparation. H.L.: conceptualization, formal analysis, and writing—review and editing. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported in part by Korea Institute of Marine Science & Technology Promotion (KIMST) funded by the Ministry of Trade, Industry and Energy in 2023 (Project Number 20210630), and in part by Innovative Human Resource Development for Local Intellectualization program through the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (IITP-2024-RS-2020-II201612, 50%).

Data Availability Statement

Data is unavailable due to the project policy.

Conflicts of Interest

The authors declare no conflict of interest.

References

Flood, M.M. The traveling-salesman problem. Oper. Res. 1956, 4, 61–75. [Google Scholar] [CrossRef]
Matai, R.; Singh, S.P.; Mittal, M.L. Traveling salesman problem: An overview of applications, formulations, and solution approaches. In Traveling Salesman Problem, Theory and Applications; Intechopen: London, UK, 2010; p. 1. [Google Scholar]
Chandra, A.; Naro, A. A Comparative Study of Metaheuristics Methods for Solving Traveling Salesman Problem. Int. J. Inf. Sci. Technol. 2022, 6, 1–7. [Google Scholar]
Croes, G.A. A Method for Solving Traveling-Salesman Problems. Oper. Res. 1958, 6, 791–812. [Google Scholar] [CrossRef]
Johnson, D.S.; McGeoch, L.A. The traveling salesman problem: A case study in local optimization. Local Search Com-Binatorial Optim. 1997, 1, 215–310. [Google Scholar]
Dorigo, M.; Maniezzo, V.; Colorni, A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. Part B Cybern. 1996, 26, 29–41. [Google Scholar] [CrossRef]
Gambardella, L.M.; Dorigo, M. Solving symmetric and a symmetric TSPs by ant colonies. In Proceedings of the IEEE International Conference on Evolutionary Computation, Nagoya, Japan, 20–22 May 1996; pp. 622–627. [Google Scholar]
Dorigo, M.; Gambardella, L. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1997, 1, 53–66. [Google Scholar] [CrossRef]
Dorigo, M.; Di Caro, G. Ant colony optimization: A new meta-heuristic. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), Washington, DC, USA, 6–9 July 1999; pp. 1470–1477. [Google Scholar]
Dorigo, M.; Birattari, M.; Stutzle, T. Ant colony optimization. IEEE Comput. Intell. Mag. 2006, 1, 28–39. [Google Scholar] [CrossRef]
Wang, Y.; Han, Z. Ant colony optimization for traveling salesman problem based on parameters optimization. Appl. Soft Comput. 2021, 107, 107439. [Google Scholar] [CrossRef]
Peker, M.; Şen, B.; Kumru, P.Y. An efficient solving of the traveling salesman problem: The ant colony system having parameters optimized by the Taguchi method. Turk. J. Electr. Eng. Comput. Sci. 2013, 21, 2015–2036. [Google Scholar] [CrossRef]
Mitchell, M. An Introduction to Genetic Algorithms; MIT Press: Cambridge, MA, USA, 1998. [Google Scholar]
Dong, X.; Cai, Y. A novel genetic algorithm for large scale colored balanced traveling salesman problem. Futur. Gener. Comput. Syst. 2019, 95, 727–742. [Google Scholar] [CrossRef]
Al Rahedi, N.T.; Atoum, J. Solving TSP problem using New Operator in Genetic Algorithms. Am. J. Appl. Sci. 2009, 6, 1586–1590. [Google Scholar]
Golberg, D.E. Genetic algorithms in search, optimization, and machine learning. Addion Wesley 1989, 102, 36. [Google Scholar]
Rao, M.R. Technical Note—A Note on the Multiple Traveling Salesmen Problem. Oper. Res. 1980, 28, 628–632. [Google Scholar] [CrossRef]
Venkatesh, P.; Singh, A. Two metaheuristic approaches for the multiple traveling salesperson problem. Appl. Soft Comput. 2015, 26, 74–89. [Google Scholar] [CrossRef]
Bellmore, M.; Hong, S. Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem. J. ACM 1974, 21, 500–504. [Google Scholar] [CrossRef]
Zheng, J.; Hong, Y.; Xu, W.; Li, W.; Chen, Y. An effective iterated two-stage heuristic algorithm for the multiple Traveling Salesmen Problem. Comput. Oper. Res. 2022, 143, 105772. [Google Scholar] [CrossRef]
Cheikhrouhou, O.; Khoufi, I. A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Comput. Sci. Rev. 2021, 40, 100369. [Google Scholar] [CrossRef]
Bektas, T. The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega 2006, 34, 209–219. [Google Scholar] [CrossRef]
Jiang, C.; Wan, Z.; Peng, Z. A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert Syst. Appl. 2019, 139, 112867. [Google Scholar] [CrossRef]
Nath, P.C.; Vaughan, D.G. Subsurface crevasse formation in glaciers and ice sheets. J. Geophys. Res. Solid Earth 2003, 108, ECV-7. [Google Scholar] [CrossRef]
Van Wyk de Vries, M.; Lea, J.M.; Ashmore, D.W. Crevasse density, orientation and temporal variability at Narsap Sermia, Greenland. J. Glaciol. 2023, 69, 1125–1137. [Google Scholar] [CrossRef]
Rasmussen, C.E.; Williams, C.K.I. Gaussian Processes for Machine Learning; MIT Press: Cambridge, MA, USA, 2006. [Google Scholar]
Kim, S.; Lee, H. Multi-Robot Task Scheduling with Ant Colony Optimization in Antarctic Environments. Sensors 2023, 23, 751. [Google Scholar] [CrossRef] [PubMed]
Kim, S.; Lee, H. Efficient Multi-task Scheduling with Nearest Neighbor Algorithm for Multi-robot Systems in Antarctic Environments. J. Inst. Control Robot. Syst. 2023, 29, 325–332. [Google Scholar] [CrossRef]
Huang, R.; Jiang, L.; Wang, H.; Yang, B. A Bidirectional Analysis Method for Extracting Glacier Crevasses from Airborne LiDAR Point Clouds. Remote Sens. 2019, 11, 2373. [Google Scholar] [CrossRef]

Figure 1. Flowchart of the proposed method.

Figure 2. An example of calculating altitude distance between nodes a and b.

Figure 3. The visualization of the concept of the probabilistic modeling of crevasses. The z-axis represents the probability of the existence of crevasses around the measured crevasses points.

Figure 4. A part of the Google map of the Antarctic environments with the virtually measured positions of crevasses represented by red areas.

Figure 5. The graphical results of the probabilistic modeling of crevasses. The areas with crevasses are probabilistically represented. The areas with higher values represented by lighter colors describe more probable areas with crevasses.

Figure 6. Experimental results of the proposed method, ACO, and GA in the Antarctic environment with 20 nodes. The proposed method produced more efficient task scheduling results with shorter total paths than the other algorithms. (a) The proposed method, (b) ACO, and (c) GA.

Figure 7. Experimental results of the proposed method, ACO, and GA in the Antarctic environment with 30 nodes. The proposed method produced more efficient task scheduling results with shorter total paths than the other algorithms. (a) Proposed method, (b) ACO, (c) GA.

Figure 8. Experimental results of the proposed method, ACO, and GA in the Antarctic environment with 40 nodes. The proposed method produced more efficient task scheduling results with shorter total paths than the other algorithms. (a) The proposed method, (b) ACO, and (c) GA.

Table 1. Comparison of the altitude distances of the methods.

Part	Proposed	ACO	GA
Node 20	98.134 km	107.938 km	105.68 km
Node 30	116.6 km	134.398 km	142.461 km
Node 40	164.766 km	186.142 km	203.56 km

Table 2. Comparison of the runtimes of the methods.

Part	Proposed	ACO	GA
Node 20	0.001 s	1.505 s	8.726 s
Node 30	0.001 s	3.980 s	12.386 s
Node 40	0.003 s	8.394 s	16.842 s

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Kang, S.; Lee, H. Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with Crevasses. Symmetry 2024, 16, 1229. https://doi.org/10.3390/sym16091229

AMA Style

Kang S, Lee H. Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with Crevasses. Symmetry. 2024; 16(9):1229. https://doi.org/10.3390/sym16091229

Chicago/Turabian Style

Kang, Seokjin, and Heoncheol Lee. 2024. "Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with Crevasses" Symmetry 16, no. 9: 1229. https://doi.org/10.3390/sym16091229

APA Style

Kang, S., & Lee, H. (2024). Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with Crevasses. Symmetry, 16(9), 1229. https://doi.org/10.3390/sym16091229

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Probabilistic Multi-Robot Task Scheduling for the Antarctic Environments with Crevasses

Abstract

1. Introduction

2. Problem Description

2.1. Antarctic Environments

2.2. Multi-Robot Scheduling Problem

2.3. The Issues of Crevasse Avoidance

3. Proposed Method

3.1. Overview

3.2. Probabilistic Cost Function with the Probabilistic Modeling of Crevasses

3.3. Multi-Robot Scheduling Method with the Probabilistic Cost Function

4. Results

Results in the Antarctic Environment

5. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI