Calculating the initial angle for a boat to pass a river in a defined direction is a common task for high school students. With the boat and the river speed values defined and constant, the students are able to calculate the direction of the initial boat vector direction and the corresponding angle relative to the riverbank. However, the task can become more complicated when additional parameters are included. The extended task can still be solved mathematically but heuristics is an alternative worth considering method. In this article both approaches are explained and compared in order to solve the task.
Recent aspects of computer science involve many ideas The task description contains following rules and ashow to optimize a system or solve a task in more com- sumptions: plex or easier way. Among methods used in computer systems heuristic approaches are very often implemen- • At the beginning the boat stays berthed at the ted. riverbank,
In [1] was resented how to use methods based on • The boat always moves in a straight direction heuristics to build user identification mechanism from with a constant speed, voice spectrum.
In [2] a compilation of heuristic methods was used • The boat is considered as a point - no boat dito detect malfunctions of lungs from ct scans, while mensions are taken into consideration, other approaches use similar algorithms in performance • The riverbanks are considered as parallel straighestimation [3] and thermal processes modelling [4, 5, ts - the river has no turns and has always the 6, 7]. In other words a spectrum of possible applica- same width, tions is very wide, and the implementation depends on the model we select for optimization. • The river flow speed is constant,
Our first results from using heuristic in sample optimization of mathematical functions were presented • The expected destination point is located at the in [8]. In this paper we would like to present how a opposite riverbank to the riverbank the boat is heuristic method can be used to solve some technical berthed to, problems. Our paper presents an application to po- When the boat starts moving in a defined direction sition boat on the river in according to the model of (represented by the angle relative to the riverbank), angle to the river bank. the river flow afects the boat movement. As a result,
We have implemented the method to solve the board- the boat moves in a direction diferent from the initial ing equation. Presented results show how the model direction. works and the discussion gives conclusion from our The result of the boat movement is reaching the opresearch. posite riverbank at some point. The distance between that point and the expected destination point is the value minimised. All the calculations described in the article are supposed to find such an initial angle for which the minimised value is the lowest possible.
ICYRIME 2020: International Conference for Young Researchers in The location of the boat destination point is assumed Informatics, Mathematics and Engineering, Online, 9 July 2020 to be measured in meters and to take any real number " bszlachta1024@gmail.com (B. Szlachta); according to the schema (Figure 1). kamirus323@student.polsl.pl (K. Rusin) The initial boat angle is measured in degrees and CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g C©Co2Em02Um0oRCnospWLyircieognhrstekfAosrthttrhiobisupptiaoPpnerr4o.b0ycIniettseeardnuatihtnioorgnsa.slU((sCeCCpEBerYUm4iR.t0te)-.dWunSde.roCrrgea)tive ttaoktehseasncyhermeaal n(Fuimgubreer2r)a.nged from 0 to 180 according
The river is assumed to flow from right to left so its vector is pointing left.
An exemplary task visualisation is presented at the Figure 3.
To sum up, the aim of the task is to calculate the angle in which the boat should start moving so that the boat reaches the opposite riverbank as close to the expected destination point as possible. In the next sections the optimal angle values will be calculated and described using the available methods: the traditional method and the heuristic method.
Before the mathematical calculations, a logical task analysis is worth considering. It makes the mathematical calculations easier to understand.
The analysis consists on manipulating the boat speed value and the river speed value. Their values, relative to each other, have an essential impact on the boat trip destination depending on the initial angle.
No other parameters values are taken into the analysis.
The relative speeds values can be split into three situations: 1. When the boat speed is larger than the river flow speed: Then, the boat can arrive to any point of the riverbank. Increasing the initial angle results in boat arriving at a point on the left side of the previous point. Similarly, decreasing the initial angle results in boat arriving at a point on the right side. 2. When the river flow speed is equal to the boat speed: Then, the boat is unable to reach any destination with non-negative coordinate. Regardless of the initial angle, the boat is always pushed to the left by the river flow. To increase the destination point location, the initial angle needs to be reduced. So, the maximal destination point location value is almost 0, reached for an angle as low as possible. 3. When the river flow speed is larger than the boat speed: Then, the boat is pushed to the left with a larger force than in the previous situation. Therefore, it is also unable to reach any destination with non-negative coordinate. An increase in the diference between the river flow speed and the boat speed results in the boat destination point location value decrease. In this situation taking too low initial angle could result in the boat being pushed to the left too much because the trip would take a lot of time. Otherwise, taking too large initial angle could also result in boat reaching a point at the very left. There exists only one initial angle for which the boat reaches a point with the largest coordinate value possible. Therefore, each point with the coordinate value lower than can be reached by taking two angles: an angle lower than and an angle larger than .
In this subsection the task will and modelled mathematically. The following parameters names are taken: • - boat speed • - river speed • ℎ - river width • - objective destination location
= | − |
(5) 5. Summing up the above points: The above points can be simplified and converted into single function declaration avoiding the temporary variables:
The aim is to find such boat initial angle for which the distance between boat trip result location and the destination point location is the lowest possible (for a The equation above can be defined as a function given parameters values). Thus, the function = ( ) ( ) = . It represents the distance between the exneeds to be determined and its optimal value(s) needs pected destination point and the actual point the boat to be found. reaches. Therefore, it is non-negative in the whole
Determining the function = ( ) is divided into domain. Due to the fact that the main expression is the following steps: bounded with an absolute value, it is not diferentiable at the point for which ( ) = 0. So, finding the func1. Determining the boat initial movement vector: The tion minimum can be split into the following steps: vector describing boat movement if there is no water flow. Having the initial angle and the boat speed the vector x-coordinate 0 and ycoordinate 0 can be determined by the following expressions: = |ℎ cos − − | sin
(6) 1. Checking the 0 value: If the boat can reach the expected destination point, then the other step does not to be proceeded and the optimal value is known. To check that, the equation ( ) = 0 needs to be solved. If there is no solution to the equation, the next step should be proceeded. 2. Calculating the function derivative: In order to ifnd the function non-zero minimum, the derivative ′( ) needs to be evaluated. Then, the solutions of the equation ′ = 0 need to be found. 0 = 0 cos 0 = 0 sin 2. Determining the boat result movement vector: The The function minimum value will be determined for vector describing the real boat movement, in- each task example separately. cluding the river flow. It can be determined by summing up the boat initial movement vector (with coordinates [ 0, 0]) and the river flow vec- 3.3. Exemplary Calculations tor (pointing left, with coordinates [ , 0]). The In this section some exemplary parameters values sets result vector x-coordinate 1 is defined by the will be defined and the optimal ( ) function value will following equation. be calculated for each set. The sets will represent each of the situations described in the logical analysis sec 1 = 0 − (3) tion.
(1) (2) (4)
The boat result movement is [ 1, 0]. 3. Determining the destination location : The location the boat reaches at the opposite riverbank.
To determine it, the Thales theorem can be used: = 1ℎ 0 1. This example is a representation of the point 1 described in section A of the article. The following parameters values are defined: Then, the objective function is defined by the following equation: ( ) = |2 4 cos − 3.5 − 1| (7)
4 sin Its plot is presented at the Figure 4. The optimal function value is 0, taken for angle ≈ 11.93◦. 2. This example is a representation of the point 2 described in section A of the article. The following parameters values are defined: • ℎ = 2 • = −0.5 Then, the objective function is defined by the following equation: ( ) = |2 4 cos − 4.5 + 0.5| (9)
4 sin Its plot is presented at the Figure 6. The optimal function value is 0.5, taken for angle ≈ 27.27◦. 4. This example is an another representation of the point 3 described in section A of the article. The following parameters values are defined:
To sum up, determining the optimal distance value using traditional mathematical methods is possible but dificult. In the next section the alternative heuristic method will be described in order to find the optimal distance.
Heuristic is a method for finding the solution. There is no guarantee that it is an optimal solution and sometimes even a correct solution. Heuristic algorithms are often used for optimization purposes, when a space of solutions is complex and common methods are impre- 4.3. Simple Local Search cise these algorithms may help.
Minimum of cost function is sometimes dificult or too time-consuming to find using mathematical methods. This is the point for which the value of function is the lowest. If our problem is too dificult to solve in usual way, heuristic algorithms can be the help we are looking for. These algorithms randomize a definite number of points and move them in a specific way. As a result, the points group in the area of the minimum of the function. The determined value should be precise enough, but we will never be able to determine the exact minimal value of the function.
There is not a one defined algorithm which is able to solve all the optimization problems. Each algorithm works in a diferent way. Their performance is based on considered functions. That is why the results of testing the heuristic functions vary from each other.
By applying the try and error method we can find the most suitable algorithm and coeficients, which we will use to find the best value of objective function.
The algorithm chosen to solve the problem is Simple Local Search - an iterative process that moves in space from the initial solution to the next according to a set rule. It generates new solutions randomly, to be more specific, agents in the neighborhood are randomly generated according to the neighborhood factor. Each algorithm start after the same number of steps gets a diferent result.
This algorithm is applied to problems from
mathematics, operations research, artificial intelligence and
also from bioinformatics. The most popular
implementations of local search are:
• Interpreting RFID tracking data for
simultaneously moving objects: an ofline sampling-based
approach [10];
• WalkSAT - solves Boolean satisfiability problems
[
The most important heuristics advantage is that the objective function is not required to fulfil any requirements. The only thing objective function needs to do is returning a value for a given argument. So, it does not need to be a mathematical function. The mathematical formula, determined in section II of the article, can be simply converted to a programming function. However, it can be determined in a diferent way - it can be defined as a procedure described by the following pseudocode:
As described in the Algorithm 1, calculating the result value is split into multiple smaller operations with saving temporary values in separate variables. This approach of calculating the result value is more humanreadable and easier to understand. • Hopfield Neural Network problem - helps in finding stable configurations [11]; • Collision free robot navigation models [12]; • Optimizing systems by using limited data [13, 14].
In other words local search is an iterative process that, after determining the starting point, moves in a step-wise manner in the search space [15]. It is a randomised, single-agent method. It consists of components such as: • goal - finding the solution with the highest value of evaluation function; • starting point - determined by an ’expert’, who can know in which direction should it go or it can be chosen randomly; • current point - a point currently under observation; • new location of current point - consists in selecting a new point from the vicinity of the current point; • neighborhood - determined by a fixed operator transforming the coordinates of the current point.
Local search sometimes gets trapped in a local optimum. There are also modifications of Local Search, which speeds up the calculation and number of iterations needed for finding the best solution, for example restart the algorithm, when no progress is observed.
Multi-start strategy - LS runs multiple times from diferent starting points. The best solution found is a global (extreme) solution. There are also various strategies of multi-start, for example strategies motivated by works on multi-armed bandit problems and Lipschitz optimization with an unknown constant [16];
Kick-start strategy - LS starts repeatedly, but not from a randomly generated point, but from a disturbed point found in the first run;
To present our results, we set the following environment parameters for three runs: • The boat speed: = 7 m/s, • The river speed: = 2.5 m/s, • The river width: ℎ = 12 meters, • The objective destination location: = 8 metres, • The boat initial range: = 112 degrees.
For the first run the following algorithm parameters were set: • The amount of iterations = 50,
As we can see in Figure 9 the Local Search finds the way to the optimum relatively fast. On the other side, when it hits the neighborhood of optimum solution it struggles to get out of it and explore deeper for even better solution.
In the second run, we changed neighborhood factor to 20 degrees to see, whether the algorithm can obtain better result while being in the optimum neighborhood. It did not work. The result is worse by 0.05 metres.
To see which parameter influences the most our implementation of Local Search we changed values of parameters. The number of agents had the greatest impact on improving the algorithm results - third run in Figure 9. The optimal value was achieved in later iterations compared to the first and second run. By increasing the value of that parameter, the algorithm can look wider and deeper for the optimum value. Thanks to this, the neighborhood of the best points is heavily explored and an even better result is found. The third line on Figure 9 shows that the algorithm has reached a distance of 0.01 meters from the destination point. This is the best possible accuracy to obtain in this version of the algorithm.
To analyze more this mathematical task, we set the following algorithm parameters, which are the same for another three tries: • The amount of iterations = 50,
As we can see in Figure 11 that try was a failure, because the boat speed was lower than the river’s. It mathematically could not be true if the destination point is located straight in front of the boat. The river stream carries the boat in the direction of its course.
In the second try the following parameters were set: • = 5 m/s, • = 3 m/s, • ℎ = 13 meters, • = 3 metres, • = 70 degrees. • = 3 m/s, • = 3 m/s, • ℎ = 15 meters, • = 3 metres, • = 90 degrees.
In that try initial angle of a boat was in diferent direction comparing to the destination point. The algorithm found its way to the optimal solution. It reached its location perfectly.
In the third try the following parameters were set: As we can see the speed of boat and river are the same, but the optimal initial angle to reach the close neighborhood of destination point is 179 degrees.
Calculating the initial angle for a boat to pass a river in a defined direction is a common task. There can be set a lot of parameters for the algorithm in mathematical modelling of this task. Our implementation takes only basic assumptions. It can be far more complicated. The local search suited very well our task. Its calculations were fast and accurate in our mathematical model.