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
ontologicallevelaproblem‐solverconsistsofthefive
majorelements[11]:
1
Aproblem‐solvinggoal.
2
Domaindatadescribingtheprobleminstance.
3
Problem‐solvingstate.
4
Problemsolvingknowledge.
5
Domainfactualknowledge.
The emphasis is given to search as the primary
techniqueusedinComputerScience andOperations
Research for solving computation‐intensive
combinatorialoptimizationproblems,typicallythose
intheNP‐hardclass[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
audienceeasilylosesthetime‐linesequence.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 step‐by‐step, differentiating
statechangesbydifferentcolours,symbols,etc.What
is more, various specialized software tools are
availabletovisualizeexplainedsearchalgorithms..
Thepsychologicalleveloftheproblemmayresult
from requirements to use programming knowledge
whencreatingastate‐space
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
two‐steps approach: the
first step consists in learning a theory together with
practicalapplicationofselectedsearchalgorithmstoa
certain problem, using pre‐designed software tools
forboth managedand self‐studyevaluation ofbasic
properties. The seconds step covers step‐by‐step
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‐Breadth‐First
Search (BFS), Depth‐First Search (DFS) and Bi‐
directionalSearch(BS),andthemorecomplexversion
that also involves Iterative‐Deepening (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
568
the search and get visualized solution(s) and all
mentioned statistics in the form of tables (Fig. 4c)
where the parameters are observed for different
Labyrinth sizes (here from 11x11 to 19x19 with the
step2).AtthemomenttheapplicationusestheSlovak
menu only (therefore some figures in this
text were
modified and/or supplemented with English
descriptions).
Figure4. The samples of the Labyrinth user interface
display(forthesize20x30)
The second version of the Labyrinth application
hasbeendesignedusingtheSWI‐Prolog6.0.0.Sinceit
assumes knowledge of the predicate calculus logics
and principles of declarative programming, the
studentsmustbefirstprovidedwiththebackground
knowledge and the practical programming skills.
That is ensured in the following advanced
courses.
Thenitispossibletobuildtheapplicationgradually,
together with the students and for particular search
algorithms.Apartofthesourcecodeforthesimpler
versionperformingtheBFS,DFS,andBSisshownin
Fig.5.
2.5
EvaluationandAnalysis
As seen above, for all selected algorithms the menu
items are created together with tables showing a
number of traversed (processed) nodes for the
defined sizes of the labyrinth, the total number of
nodesstoredinthememory,themaximumnumberof
nodestobeprocessedatthemomentandthe
shareof
solutions with the minimum path. Data obtained in
this way may be used to show dependence of
traversednodesonthelabyrinthdimensions,shareof
theshortestpossiblesolutionsandusageofmemory
bythegivenalgorithm.
Figure5. A part of the SWI‐Prolog source code for the
Labyrinthapplication(withBFS,DFS,BS)
Figure6. Graphical representation of the search algorithm
characteristics(BFSexample)
To explain the meaning of data obtained in the
table form (Fig. 4c), the characteristics of the
individual search algorithms could be presented in
thegraphicalform(Fig.6).
For the sake of mutual comparison of time
complexity statistic data might be processed and
presented in the form of a graph,
elaborated e.g. in
the Matlab environment (Fig. 7). Thus one could
deducethatthemosttimedemandingmethodsseem
tobeIDandBTalgorithms.Forthelabyrinthsize100
x100theytraversemorethan30000(ID),resp.4000
nodes (BT). Time complexity grows exponentially.
Theyare
followedbytheUCSalgorithmwhichhasa
little bit less steep increase of search time and for
maximal sizes of the labyrinth it traverses
approximately2500nodes.Timecomplexityofother
testedmethodsisalmostthesame,i.e. intheorderof
hundredsnodesforthemaximallabyrinthsize(about
200traversednodesfortheGSupto800nodesforthe
Dijkstraalgorithm).
569
Figure7.Thenumberoftraversednodesdependingonthe
Labyrinthsize
To evaluate space complexity one must take into
account difference between the totally consumed
memory space (Fig. 8) and the actually allocated
spaceintheoperationmemory(Fig.9).
Figure8. Total operational memory acquisition depending
ontheLabyrinthsize
For considerably big state spaces (unlike our
Labyrinth application) data could be stored to a
permanent memory (e.g. hardisk) and thus to save
operation memory. While methods of the best first
search(UCS,GS,A*)showconsiderabletotalmemory
consumption(ifcomparedwithuninformedmethods)
their consumption of operation memory is
comparable. The most space demanding method is
theDijkstraalgorithmwhichworkswithallnodesin
the state space during every cycle (for the
backtrackingalgorithmthespacecomplexityhasnot
been evaluated since in the Labyrinth application it
wasimplementedwiththemin.spacecomplexity,i.e.
workingwith1
nodeinthememoryonly).Sincethe
uninformed methods cannot find the shortest path
throughthemazefromtheviewpointofitslengthbut
onlyfromtheviewpointofnumberofnodes,theonly
acceptable methods in the application remain the
UCS,A*,andDijkstraalgorithms.
The given graph (Fig. 10)
indicates that
uninformed methods with growing size of the state
space very quickly loose capability of finding an
optimal path. On the other side, if only 1 solution
exists,thispropertybecomesirrelevant(i.e.ifonly1
path is available in our Labyrinth application).
Globally, the small space complexity of
uninformed
methodscouldbeconfirmed;however,theirusability
is limited to those tasks where optimal solution is
needed or tasks in which they are able to provide
acceptable solution without any additional
information.WithintheallacceptablemethodstheA*
algorithmseemstobethebestifconsideringitstime
complexity
because its space complexity is also
acceptable.
Figure9.Actualoperationalmemoryacquisitiondepending
ontheLabyrinthsize
Figure10. Share of the optimal solutions (optimality
criterion:thepathlength)
3 ACKNOWLEDGMENTS
ThisworkwassupportedbytheSlovakgrantagency
KEGA under the project “KEGA 010U‐4/2013
Modernization of didactic equipment and teaching
methods with a focus on the area of roboticsʺ. The
authors thank M.S. Ivan Sakál for his technical help
andsoftwaresupport.
4
CONCLUSION
Thepaperdemonstratedaneducationalaspectofhow
formaltaskssolvedthroughsearchalgorithmscould
be modelled, tested and evaluated. As a working
example the Labyrinth authoring software tool has
beendiscussed,implementedinbothdeclarativeand
proceduralways(SWIPrologandJava).Ithelpedto
obtain statistic data usable
for evaluation of applied
methods. The set of tested methods included most
usualsearchalgorithms.
REFERENCES
[1] R. A. Akerkar, and P. S. Sajja. Knowledge‐Based
Systems.Jones&BartlettLearning,2010.
[2] Artificial Intelligence Applications to Critical
Transportation Issues. TRC E‐C168. November 2012.
http://onlinepubs.trb.org/onlinepubs/circulars/ec168.pdf
[3] D. O. Marlow and J. E. Murphy. Testing various
backtracking algorithms in airborne maritime
570
surveillance modelling. In 20th International Congress
on Modelling and Simulation, Adelaide, Australia, 1–6
December 2013.
http://www.mssanz.org.au/modsim2013/D1/marlow.pdf
[4]Kilby,P.,Tobin,P.,Luscombe,R.,Barry,S.andHickson,
R.Themaritimesurveillanceproblem.InT.R.Marchant,
M.EdwardsandG.N.Mercer(eds.), Proceedingsofthe
2007Mathematics‐in‐IndustryStudyGroup,32
‐56,2008
[5] S.RussellandP.Norvig.Solvingproblemsbysearching
in Artificial Intelligence. A Modern Approach, 3rd ed.
NewJersey:PrenticeHall,2010,ch.3,pp.64–119.
[6] D. S. Touretzky. Preparing computer science students
for the robotics revolution. Communications of the
ACM.53(8):27‐29,2010.
[7]
T. W. Neller, C. G. Presser, I. Russell, and Z. Markov.
Pedagogical possibilities for the dice game pig. J.
Comput.SmallColl.21(6),149‐161,2006.
[8] D. Wong, R. Zink, and S. Koenig. Teaching Artificial
IntelligenceandRoboticsviaGames(Abstract).InAAAI
Symposium on EAAI 2010,
http://www.cs.huji.ac.il/~jeff/aaai10/02/AAAI10‐342.pdf
[9]
M. Zyda and S. Koenig. Teaching artificial intelligence
playfully. In Proc. AAAI‐08 Education Colloquium,
pages90‐95,2008.
[10]P.J.Muñoz‐Merino,M.F.Molina, M.Muñoz‐Organero
and C. D. Kloos. Motivation and Emotions in
Competition Systems for Education: An Empirical
Study. IEEE Transactions on education. 57(3):
182‐187,
2014.
[11] B. Chandrasekaran, J. R. Josephson, and V. R.
Benjamins. What are ontologies, and why do we need
them?IEEEIntelligentSystems.1(4):20–26,1999.
[12] W. Zhang. State Space Search for Problem Solving.
StateSpaceSearch.Algorithms,Complexity,Extensions,
and Applications. 1st ed. New York: Springer‐Verlag,
1999.
[13] R.Varelaand E.Soto.Schedulingas heuristic search
withstatespacerevolution.LectureNotesinComputer
Science.2527:815‐824,2002.
[14] G. Kovásznai and G. Kusper. Artificial Intelligence
and its teaching. 1st ed., 1990
http://aries.ektf.hu/~gkusper/ArtificialIntelligence_Lectu
reNotes.v.1.0.4.pdf
[15] S. M. Lord, R. A. Layton, and M. W. Ohland.
Trajectories of Electrical Engineering and Computer
Engineering Students by Race and Gender. IEEE
Transactionsoneducation.54(4):610‐618,2011.
