565
1
INTRODUCTION
The ability to create and use an internal machine
model of the world is an important feature of
ʺintelligentʺ systems profiting from artificial
intelligence (AI) components. If initial and goal
models of the world are available, the AI system is
expected to solve the problem, i.e. to find a proper
sequenceofactionsdetermininghowtogetfromthe
initialtothegoalmodel.Sinceinmanycasesacertain
level of abstraction is necessary to simplify the
problem, one can take advantage of state space
representation.Thusthestatespacecanbeseenasa
set of states of
the problem to which we can get by
applyingoperatorstoaparticularstateoftheproblem
to get a new state (or remain in the same state).
Transitions between models may be represented by
transitionsbetweenstates.Torepresentastatespace
onemayuseanorientedgraphconsisting
ofvertices
(nodes) and edges. Each vertex of the graph is a
completedescriptionofthestate.Thestatespacecan
behugeduetothecombinatorialexplosion.Problem
solution then may be formulated as a search of the
paththroughadirectedgraphunderfulfillingcertain
conditions. Those states in
which more transitions
(rules) might potentially be applied bring conflicts.
The way of how the conflict could be solved is
defined by the used control mechanism (problem
solvingmethod).Taskssolvedintherealworldmay
cover searching paths, optimizing electrical circuits,
cryptography, planning, configuring routes, etc.
Generally, there are
different kinds of tasks
(problems)tobegenerallyaddressed:mundanetasks
such as perception (e.g. vision, speech), natural
languageprocessing(e.g.understanding, generation,
translation), common sense reasoning or robot
control; formal tasks such as games (e.g. chess,
checkers,Sudoku,etc.)ormathematics(e.g.geometry,
logic,integralcalculusetc.);andexperttasks
suchas
engineering(e.g.design,faultfinding,manufacturing
planning, etc.), scientific analysis, medical analysis,
financial analysis, and many others [1]. Considering
relevance of the presented topic to the main area
TransNavinterests,wecanmentionageneralsurvey
ofAIapplicationstocriticaltransportationissues[2]
or particular problems of
maritime surveillance
Learning Search Algorithms: An Educational View
A.Janota,V.Šimák&J.Hrbček
FacultyofElectricalEngineering,UniversityofŽilina,Slovakia
ABSTRACT:Artificialintelligencemethodsfindtheirpracticalusageinmanyapplicationsincludingmaritime
industry. The paper concentrates on the methods of uninformed and informed search, potentiallyusable in
solvingofcomplexproblemsbasedonthestatespacerepresentation.Theproblemofintroducingthesearch
algorithmstonewcomershasitstechnicaland
psychologicaldimensions.Theauthorsshowhowitispossible
to cope with both of them through design and use of specialized authoring systems. A typical example of
searching a path through the maze is used to demonstrate how to test, observe and compare properties of
varioussearchstrategies.Performanceof
searchmethodsisevaluatedbasedonthecommoncriteria.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 8
Number 4
December 2014
DOI:10.12716/1001.08.04.11
566
modelling(e.g.testingofbacktrackingalgorithms[3]
or,treatingtheproblemasavariationofaTravelling
SalesmanProblem[4]).
The AI courses at the universities are provided
based on standard sources such as e.g. [5], however
many different approaches to teaching AI can be
found around the world.
Several introductory
programming courses use problems in AI as
motivating examples [6][7]; the AI is often being
taught through the games to attract more students
intocomputing[8][9].Motivationisakeyfactorinthe
learning process [10]. To make students properly
motivated, specialized education software tools can
bedeveloped
andusedtodemonstrateselectedsearch
strategiesthroughtypicalproblemssuchassearching
path through the maze, shortest path in a graph,
Sudoku, etc. In this paper an authoring tool, called
“Labyrinth”, is used as a working example. The
Labyrinthapplicationhasbeenimplementedinboth
declarative and procedural ways (SWI
Prolog and
Java)andhelpstodemonstrateproblemsolvingand
toobtainstatisticdataneededforfurtherevaluation.
The set of tested methods includes the most usual
searchalgorithmswhichmaybetested,observedand
theirpropertiescomparednotonlytheoretically,but
also practically. Performance of particular searching
methods in
a state space is evaluated based on the
common criteria, i.e. completeness, time complexity,
spacecomplexityandoptimality.
2
DESIGNOFTHEAUTHORINGSOFTWARE
SYSTEM
2.1
GeneralFormulationoftheTask
Personswhowanttoknowhowtosolve tasksfrom
above categories must master perceptual, linguistic
and common sense skills, followed by skills
characterizing the application domain. On the
ontologicallevelaproblemsolverconsistsofthefive
majorelements[11]:
1
Aproblemsolvinggoal.
2
Domaindatadescribingtheprobleminstance.
3
Problemsolvingstate.
4
Problemsolvingknowledge.
5
Domainfactualknowledge.
The emphasis is given to search as the primary
techniqueusedinComputerScience andOperations
Research for solving computationintensive
combinatorialoptimizationproblems,typicallythose
intheNPhardclass[12].Statespacesearchinghasa
numberofinterestingproperties,suchastheabilityto
guarantee optimal
solutions and the possibility of
exploiting domain knowledge to guide the search
[13]. The core of the search problems isʺHow to
controlthesearch?“.Atthebeginningthereisgiven:
1
AnInitialStatethattheproblemstartsin.
2
Asetofoperatorsthatcanbetaken.
3
A Goal State (or a set of Goal States) that the
problemendsin.
4
Optionally, paths Cost function to solve the
problem.
The task is formulated as finding a sequence of
operators leading from the Initial State to the Goal
State.Thesearchspaceisatree(graph)definedbythe
initialstateandtheoperators.Thesearchtree(graph)
isanexplicittreegenerated
duringthesearchbythe
control strategy. Different search algorithms use
different search strategies. Generally, they may be
either uninformed (make no use of domain
knowledge‐alsoknownasblindsearch)orinformed
(using some rule(s) of thumb). The task could be
expressedasaGeneralSearchalgorithm,consistingof
thefollowingsteps:
1
Initializethesearchtreewiththeinitialstate.
2
Reportfailureifsearchtreeisempty.
3
Movetoaleafnodeaccordingtoastrategy.
4
Readyifagoalstate.
5
Expandthecurrentstatebygeneratingsuccessors
tothecurrentstate.Addthemtothesearchtreeas
leaves.
6
Repeatfrom2.
For the sake of simplicity the more formal
(mathematical) definitions of algorithms and state
spaces have been intentionally avoided here since
they are available in many AI textbooks. Generally,
thesearchstrategiesapplythefollowingfourcriteria:
1
Completeness:isfindingasolutionguaranteed?
2
Timecomplexity:Howlongdotheytakeinsearch
time?(Whatisanumberofgeneratednodes?).
3
Space complexity: Storage required? (How many
nodesaretobestoredinamemory?).
4
Optimality:Whenthereareseveralsolutions,does
itfindthebestone?
2.2
TheProblem
Representingsearchalgorithmsthroughthestateofa
vertexisdifficultsinceitisconstantlychanging(e.g.a
vertex can be unexplored, open or closed) and the
audienceeasilylosesthetimelinesequence.Thusthe
problem has two levels, one that is technical and
anotherthatispsychological[14].
There
are different approaches how to cope with
the technical side of the problem to use colourful
figures; to visualize a changing tree through
multimedia means (animations, videos); or to apply
interactive programs solving particular problems.
Very often animated figures are used as a part of
presentations, where the algorithms
and the graphs
can be seen developed stepbystep, differentiating
statechangesbydifferentcolours,symbols,etc.What
is more, various specialized software tools are
availabletovisualizeexplainedsearchalgorithms..
Thepsychologicalleveloftheproblemmayresult
from requirements to use programming knowledge
whencreatingastatespace
representationalongwith
the attached data structures and selecting the
appropriatealgorithmthatisrecursiveinmanycases.
Since the length of the solution is not determinable
beforehand, its storing requires a dynamic data
structure[14].
Potential solution of both sides of the learning
problem can be seen in the
twosteps approach: the
first step consists in learning a theory together with
practicalapplicationofselectedsearchalgorithmstoa
certain problem, using predesigned software tools
forboth managedand selfstudyevaluation ofbasic
properties. The seconds step covers stepbystep
solution (programming) of problems with gradually
567
growing complexity by already known search
algorithms. For that purpose a basic course in a
proper programming language (in our case SWI
Prolog) must be provided. Finally, obtained
knowledge may be utilised in own individual
projects.
Obviously, modifications and depth of provided
knowledge depends on what kind of future
profession
is to be addressed (electrical engineering,
computer engineering, transport engineering, etc.).
Details on trajectories of electrical engineering and
computer engineering students by race and gender
canbefoundin[15].
2.3
SystemConcept
The attention here is paid to the application called
Labyrinth. The problem consists in finding a path
through the maze. Considering the facts mentioned
above, the application should make us possible to
generate a labyrinth structure of the required size
(different dimension/complexity of the problem).
Then,forthegeneratedconfiguration,the
InitialState
mustbedefinedinsuchaway thatallcrossingand
terminalpointsaregivenlettersrepresentingnodesin
thestatespace(Fig.1).
Figure1. Example of marking nodes in a generated
Labyrinthconfiguration
Thismakespossibletocreateamodelofthestate
space. The nodes (vertices) represent names of the
crossingsandterminalpointsofpathsandtransition
values correspond to distances between the nodes
(Fig.2).
TwoversionsoftheauthoringtoolLabyrinthhave
been developed so far: the simpler version which
provides only 3 types of algorithms‐BreadthFirst
Search (BFS), DepthFirst Search (DFS) and Bi
directionalSearch(BS),andthemorecomplexversion
that also involves IterativeDeepening (ID),
Backtracking (BT), Uniform Cost Search (UCS),
GreedySearch(GS),A*,andDijkstraalgorithms.
As the first step it is necessary
to make initial
settings of the Labyrinth application. The more
complexversionincludes:
1
Selectionofthesearchalgorithmtypestobeused.
2
Definition of the labyrinth dimensions (width *
height).
3
Definition of the step size (for statistics
calculations).
4
Enabling or disabling the optionʺFind more
solutionsʺ.
5
Accuracyofobtaineddata.
Figure2. Example of marking nodes in a generated
Labyrinthconfiguration
Figure3. Different solutions found by the Labyrinth
application
Based on the settings above it is possible to
generate the maze structure and write relevant data
into the log file. All solutions found for particularly
usedsearch strategiescan be visualized and seen in
theirgraphicalrepresentations(Fig.3).
2.4
Implementation
The Labyrinth tool has been developed in several
versions(simplerandmorecomplex),andalsousing
different programming approaches‐procedural and
declarativeones.
The Java version (Fig. 3, 4) plays the motivation
role and makes possible to show and evaluate basic
parametersofmentionedsearchstrategiesappliedto
theLabyrinthproblem
inthebasicpartofthecourse.
The application was created in the Eclipse
environment(EclipseStandard/SDK,Version:Kepler
Service Release 1). To run it the Java package (min.
version7,update45)mustbeinstalled.
Asindicatedabove,atthebeginningtheusermay
definetherequiredsizeof
theLabyrinththroughthe
“height * width” setting available from the main
window(Fig.4a)andafterconfirminghis/hersettings
automatically generate its random structure. Then
there is a chance to set other preferences that
determine the range of evaluated statistic data (Fig.
4b):singleormultiplesolutions,requiredtypesof
the
searchalgorithms,accuracy,min.andmax.sizeofthe
Labyrinthandthestepsize.Thenitispossibletorun