=Paper=
{{Paper
|id=Vol-2768/paper5
|storemode=property
|title=Finding The Optimal Boat Direction Using Heuristics
|pdfUrl=https://ceur-ws.org/Vol-2768/p5.pdf
|volume=Vol-2768
|authors=Bartlomiej Szlachta,Kamil Rusin
}}
==Finding The Optimal Boat Direction Using Heuristics==
https://ceur-ws.org/Vol-2768/p5.pdf
Finding The Optimal Boat Direction Using Heuristics
Bartlomiej Szlachtaa , Kamil Rusina
a Faculty of Applied Mathematics, Silesian University of Technology, Kaszubska 23, Gliwice, 44-100, Poland
Abstract
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.
Keywords
Heuristics, optimization, boat, calculating initial angle, heuristic methods, local search
1. Introduction 2. Model setting
Recent aspects of computer science involve many ideas The task description contains following rules and as-
how to optimize a system or solve a task in more com- sumptions:
plex or easier way. Among methods used in computer
• At the beginning the boat stays berthed at the
systems heuristic approaches are very often implemen-
riverbank,
ted.
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 di-
to 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 straigh-
estimation [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 op-
timization 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 affects the boat movement. As a result,
We have implemented the method to solve the board- the boat moves in a direction different 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 op-
research. 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
© 2020 Copyright for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
takes any real number ranged from 0 to 180 according
CEUR
Workshop
CEUR Workshop Proceedings (CEUR-WS.org)
Proceedings
http://ceur-ws.org
ISSN 1613-0073
to the schema (Figure 2).
3. Traditional approach
3.1. Preliminary Analysis
Before the mathematical calculations, a logical task ana-
Figure 1: Destination location schema lysis 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 anal-
ysis.
The relative speeds values can be split into three sit-
uations:
Figure 2: Initial angle schema
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 re-
sults 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 des-
Figure 3: Exemplary task visualisation
tination with non-negative coordinate. Regard-
less of the initial angle, the boat is always pushed
to the left by the river flow. To increase the desti-
The task results differ depending on the following nation point location, the initial angle needs to
task parameters: be reduced. So, the maximal destination point
• The boat speed, measured in m/s, positive real location value is almost 0, reached for an angle
number, as low as possible.
• The river speed, measured in m/s positive real 3. When the river flow speed is larger than the boat
number, speed: Then, the boat is pushed to the left with a
larger force than in the previous situation. There-
• The river width, measured in meters, positive fore, it is also unable to reach any destination
real number, with non-negative coordinate. An increase in
• Expected destination point location, measured the difference between the river flow speed and
in meters, any real number, the boat speed results in the boat destination
point location value decrease. In this situation
The river is assumed to flow from right to left so its taking too low initial angle could result in the
vector is pointing left. boat being pushed to the left too much because
An exemplary task visualisation is presented at the the trip would take a lot of time. Otherwise,
Figure 3. taking too large initial angle could also result
To sum up, the aim of the task is to calculate the an- in boat reaching a point at the very left. There
gle in which the boat should start moving so that the exists only one initial angle for which the boat
boat reaches the opposite riverbank as close to the ex- reaches a point 𝑥𝑏𝑖𝑔 with the largest coordinate
pected destination point as possible. In the next sec- value possible. Therefore, each point with the
tions the optimal angle values will be calculated and coordinate value lower than 𝑥𝑏𝑖𝑔 can be reached
described using the available methods: the traditional by taking two angles: an angle lower than 𝑥𝑏𝑖𝑔
method and the heuristic method. and an angle larger than 𝑥𝑏𝑖𝑔 .
27
3.2. Determining Objective Function 4. Determining the distance 𝑟: The distance between
boat trip result location and the destination point
In this subsection the task will and modelled mathe-
location.
matically. The following parameters names are taken:
𝑟 = |𝑥𝑟 − 𝑥𝑑 | (5)
• 𝑣𝑏 - boat speed
• 𝑣𝑟 - river speed
5. Summing up the above points: The above points
• ℎ - river width can be simplified and converted into single func-
tion declaration avoiding the temporary variables:
• 𝑥𝑑 - objective destination location
𝑣 cos 𝛼 − 𝑣𝑟
The aim is to find such boat initial angle 𝛼 for which 𝑟 = |ℎ 𝑏 − 𝑥𝑑 | (6)
𝑣𝑏 sin 𝛼
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 ex-
needs 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 differentiable
at the point for which 𝑓 (𝛼) = 0. So, finding the func-
1. 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 1. Checking the 0 value: If the boat can reach the
boat speed 𝑣𝑏 the vector x-coordinate 𝑥0 and y- expected destination point, then the other step
coordinate 𝑦0 can be determined by the follow- does not to be proceeded and the optimal value
ing expressions: is known. To check that, the equation 𝑓 (𝛼) = 0
needs to be solved. If there is no solution to the
𝑥0 = 𝑣0 cos 𝛼 (1) equation, the next step should be proceeded.
2. Calculating the function derivative: In order to
𝑦0 = 𝑣0 sin 𝛼 (2)
find the function non-zero minimum, the deriva-
tive 𝑟 ′ (𝛼) needs to be evaluated. Then, the solu-
tions of the equation 𝑟 ′ = 0 need to be found.
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.
The boat result movement is [𝑥1 , 𝑦0 ]. 1. This example is a representation of the point 1
described in section A of the article. The follow-
3. Determining the destination location 𝑥𝑟 : The lo- ing parameters values are defined:
cation the boat reaches at the opposite riverbank.
• 𝑣𝑏 = 4
To determine it, the Thales theorem can be used:
• 𝑣𝑟 = 3.5
𝑥1 ℎ
𝑥𝑟 = (4) • ℎ=2
𝑦0
• 𝑥𝑑 = 1
28
Figure 4: Function representation with the parame- Figure 6: Function representation with the parame-
ters set 1 ters set 3
Figure 5: Function representation with the parame- Figure 7: Function representation with the parame-
ters set 2 ters set 4
Then, the objective function is defined by the • 𝑣𝑟 = 4.5
following equation: • ℎ=2
4 cos 𝛼 − 3.5 • 𝑥𝑑 = −0.5
𝑓 (𝛼) = |2 − 1| (7)
4 sin 𝛼 Then, the objective function is defined by the
Its plot is presented at the Figure 4. The optimal following equation:
function value is 0, taken for angle 𝛼 ≈ 11.93◦ . 4 cos 𝛼 − 4.5
2. This example is a representation of the point 2 𝑓 (𝛼) = |2 + 0.5| (9)
4 sin 𝛼
described in section A of the article. The follow-
ing parameters values are defined: Its plot is presented at the Figure 6. The optimal
function value is 0.5, taken for angle 𝛼 ≈ 27.27◦ .
• 𝑣𝑏 = 4
4. This example is an another representation of the
• 𝑣𝑟 = 4 point 3 described in section A of the article. The
• ℎ=2 following parameters values are defined:
• 𝑥𝑑 = 0.5 • 𝑣𝑏 = 4
Then, the objective function is defined by the • 𝑣𝑟 = 8
following equation: • ℎ=2
4 cos 𝛼 − 4 • 𝑥𝑑 = −5
𝑓 (𝛼) = |2 − 0.5| (8)
4 sin 𝛼 Then, the objective function is defined by the
Its plot is presented at the Figure 5. The optimal following equation:
function value is almost 0.5, taken for angle 𝛼 ≈ 4 cos 𝛼 − 8
0◦ . 𝑓 (𝛼) = |2 + 5| (10)
4 sin 𝛼
3. This example is one of the representations of the
point 3 described in section A of the article. The Its plot is presented at the Figure 7. The optimal
following parameters values are defined: function value is 0, taken for angles 𝛼 ≈ 110.22◦
and 𝛼 ≈ 26.17◦ .
• 𝑣𝑏 = 4
29
To sum up, determining the optimal distance value
using traditional mathematical methods is possible but
difficult. In the next section the alternative heuristic
method will be described in order to find the optimal
distance.
4. Heuristic approach
4.1. Heuristics - Introduction
Heuristic is a method for finding the solution. There is
no guarantee that it is an optimal solution and some-
times 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 difficult or The algorithm chosen to solve the problem is Simple
too time-consuming to find using mathematical meth- Local Search - an iterative process that moves in space
ods. This is the point for which the value of function from the initial solution to the next according to a set
is the lowest. If our problem is too difficult to solve rule. It generates new solutions randomly, to be more
in usual way, heuristic algorithms can be the help we specific, agents in the neighborhood are randomly gen-
are looking for. These algorithms randomize a definite erated according to the neighborhood factor. Each al-
number of points and move them in a specific way. As gorithm start after the same number of steps gets a
a result, the points group in the area of the minimum different result.
of the function. The determined value should be pre- This algorithm is applied to problems from mathe-
cise enough, but we will never be able to determine matics, operations research, artificial intelligence and
the exact minimal value of the function. also from bioinformatics. The most popular imple-
There is not a one defined algorithm which is able mentations of local search are:
to solve all the optimization problems. Each algorithm • WalkSAT - solves Boolean satisfiability problems
works in a different way. Their performance is based [9];
on considered functions. That is why the results of
testing the heuristic functions vary from each other. • Interpreting RFID tracking data for simultane-
By applying the try and error method we can find the ously moving objects: an offline sampling-based
most suitable algorithm and coefficients, which we will approach [10];
use to find the best value of objective function.
• Hopfield Neural Network problem - helps in find-
ing stable configurations [11];
4.2. Determining Objective Function
• Collision free robot navigation models [12];
The most important heuristics advantage is that the
objective function is not required to fulfil any require- • Optimizing systems by using limited data [13,
ments. The only thing objective function needs to do is 14].
returning a value for a given argument. So, it does not
need to be a mathematical function. The mathematical In other words local search is an iterative process
formula, determined in section II of the article, can be that, after determining the starting point, moves in a
simply converted to a programming function. How- step-wise manner in the search space [15]. It is a ran-
ever, it can be determined in a different way - it can domised, single-agent method. It consists of compo-
be defined as a procedure described by the following nents such as:
pseudocode: • goal - finding the solution with the highest value
As described in the Algorithm 1, calculating the re- of evaluation function;
sult value is split into multiple smaller operations with
saving temporary values in separate variables. This • starting point - determined by an ’expert’, who
approach of calculating the result value is more human- can know in which direction should it go or it
readable and easier to understand. can be chosen randomly;
30
• current point - a point currently under observa-
tion;
• new location of current point - consists in select-
ing 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 op-
timum. There are also modifications of Local Search,
which speeds up the calculation and number of itera- Figure 8: Angles in each iteration
tions needed for finding the best solution, for example
restart the algorithm, when no progress is observed.
Multi-start strategy - LS runs multiple times from
different starting points. The best solution found is a
global (extreme) solution. There are also various strate-
gies 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;
4.4. Exemplary Heuristic Results
Figure 9: Distance from destination in each iteration
To present our results, we set the following environ-
ment parameters for three runs:
• The boat speed: 𝑣𝑏 = 7 m/s, In the second run, we changed neighborhood factor
to 20 degrees to see, whether the algorithm can ob-
• The river speed: 𝑣𝑟 = 2.5 m/s, tain better result while being in the optimum neigh-
• The river width: ℎ = 12 meters, borhood. It did not work. The result is worse by 0.05
metres.
• The objective destination location: 𝑥𝑑 = 8 me- To see which parameter influences the most our im-
tres, plementation of Local Search we changed values of pa-
rameters. The number of agents had the greatest im-
• The boat initial range: 𝛼𝑏 = 112 degrees. pact on improving the algorithm results - third run in
For the first run the following algorithm parameters Figure 9. The optimal value was achieved in later it-
were set: erations compared to the first and second run. By in-
creasing the value of that parameter, the algorithm can
• The amount of iterations = 50, look wider and deeper for the optimum value. Thanks
to this, the neighborhood of the best points is heavily
• The amount of agents = 10, explored and an even better result is found. The third
line on Figure 9 shows that the algorithm has reached
• The neighborhood factor = 7 degrees.
a distance of 0.01 meters from the destination point.
As we can see in Figure 9 the Local Search finds the This is the best possible accuracy to obtain in this ver-
way to the optimum relatively fast. On the other side, sion of the algorithm.
when it hits the neighborhood of optimum solution it To analyze more this mathematical task, we set the
struggles to get out of it and explore deeper for even following algorithm parameters, which are the same
better solution. for another three tries:
• The amount of iterations = 50,
31
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,
Figure 10: Angles in each iteration
• 𝑥𝑑 = 3 metres,
• 𝛼𝑏 = 70 degrees.
In that try initial angle of a boat was in different di-
rection comparing to the destination point. The algo-
rithm found its way to the optimal solution. It reached
its location perfectly.
In the third try the following parameters were set:
• 𝑣𝑏 = 3 m/s,
• 𝑣𝑟 = 3 m/s,
• ℎ = 15 meters,
Figure 11: Distance from destination in each iteration
• 𝑥𝑑 = 3 metres,
• 𝛼𝑏 = 90 degrees.
• The amount of agents = 10,
As we can see the speed of boat and river are the
• The neighborhood factor = 7 degrees.
same, but the optimal initial angle to reach the close
In the first try, we set the following parameters: neighborhood of destination point is 179 degrees.
• 𝑣𝑏 = 2 m/s,
5. Conclusion
• 𝑣𝑟 = 3 m/s,
Calculating the initial angle for a boat to pass a river in
• ℎ = 13 m, a defined direction is a common task. There can be set
a lot of parameters for the algorithm in mathematical
• 𝑥𝑑 = 5 m,
modelling of this task. Our implementation takes only
• 𝛼𝑏 = 122 degrees. 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.
32
References [9] T. Fantasy, R. Riehm, J. Zhao, A parallel walk-
sat solution to the boolean satisfiability problem
[1] D. Połap, M. Woźniak, R. Damaševičius, (2018).
R. Maskeliūnas, Bio-inspired voice evaluation [10] B. Fazzinga, S. Flesca, F. Furfaro, F. Parisi, In-
mechanism, Applied Soft Computing 80 (2019) terpreting rfid tracking data for simultaneously
342–357. moving objects: an offline sampling-based ap-
[2] M. Woźniak, D. Połap, Bio-inspired methods proach, Expert Systems with Applications (2020)
modeled for respiratory disease detection from 113368.
medical images, Swarm and evolutionary com- [11] N.-e. Joudar, Z. En-Naimani, M. Ettaouil, Using
putation 41 (2018) 69–96. continuous hopfield neural network for solving
[3] G. Capizzi, S. Coco, G. L. Sciuto, C. Napoli, a new optimization architecture model of proba-
W. Hołubowski, An entropy evaluation algo- bilistic self organizing map, Neurocomputing 344
rithm to improve transmission efficiency of com- (2019) 82–91.
pressed data in pervasive healthcare mobile sen- [12] E. Krell, A. Sheta, A. P. R. Balasubramanian, S. A.
sor networks, IEEE Access 8 (2019) 4668–4678. King, Collision-free autonomous robot naviga-
[4] A. Zielonka, E. Hetmaniok, D. Słota, Reconstruc- tion in unknown environments utilizing pso for
tion of the boundary condition in the binary al- path planning, Journal of Artificial Intelligence
loy solidification problem with the macrosegre- and Soft Computing Research 9 (2019) 267–282.
gation and the material shrinkage phenomena [13] G. Tambouratzis, M. Vassiliou, Swarm algo-
taken into account, Heat Transfer Engineering rithms for nlp-the case of limited training data,
(2019) 1–11. Journal of Artificial Intelligence and Soft Com-
[5] B. A. Nowak, R. K. Nowicki, M. Woźniak, puting Research 9 (2019) 219–234.
C. Napoli, Multi-class nearest neighbour classi- [14] F. Bonanno, G. Capizzi, G. Sciuto, C. Napoli,
fier for incomplete data handling, in: Interna- Wavelet recurrent neural network with semi-
tional Conference on Artificial Intelligence and parametric input data preprocessing for micro-
Soft Computing, Springer, 2015, pp. 469–480. wind power forecasting in integrated generation
[6] G. Capizzi, G. Lo Sciuto, G. Cammarata, M. Cam- systems, in: 5th International Conference on
marata, Thermal transients simulations of a Clean Electrical Power: Renewable Energy Re-
building by a dynamic model based on thermal- sources Impact, ICCEP 2015, 2015, pp. 602–609.
electrical analogy: Evaluation and implementa- [15] G. Bianco, R. Giuliano, G. Marrocco, F. Mazzenga,
tion issue, Applied Energy 199 (2017) 323–334. A. Mejia-Aguilar, Lora system for search and res-
[7] A. Fornaia, C. Napoli, E. Tramontana, Cloud cue: Path loss models and procedures in moun-
services for on-demand vehicles management, tain scenarios, IEEE Internet of Things Journal
Information Technology and Control 46 (2017) (2020).
484–498. [16] S. Bubeck, G. Stoltz, J. Y. Yu, Lipschitz ban-
[8] B. Szlachta, K. Rusin, Ł. Płaneta, Selected heuris- dits without the lipschitz constant, in: Interna-
tic algorithms analysis and comparison in solv- tional Conference on Algorithmic Learning The-
ing optimization problems (2018). ory, Springer, 2011, pp. 144–158.
33