Uniform-Cost Search Algorithm in the AI Environment

Uniform Cost Search (UCS) is a popular search algorithm used in artificial intelligence (AI) for finding the least cost path in a graph.

1. Uniform Cost Search for
Optimal Path
AI Lab
School of Computer Engineering
Dr Hitesh Mohapatra
Associate Professor
KIIT University

2. Assignment 4: Uniform Cost Search for
Optimal Path
•Objective:
•Implement Uniform Cost Search for a weighted graph.
•Problem Statement: Given a weighted graph (e.g., a transportation network with travel costs),
find the minimum-cost path between two nodes.
•Tasks:
1.Represent the graph as an adjacency list.
2.Implement Uniform Cost Search to find the optimal path.
3.Compare it with BFS for unweighted graphs.

3. Definition
•UniformCostSearch(UCS)isapopularsearchalgorithmused
inartificialintelligence(AI)forfindingtheleastcostpathina
graph.
•ItisavariantofDijkstra'salgorithmandisparticularlyuseful
whenalledgesofthegraphhavedifferentweights,andthe
goalistofindthepathwiththeminimumtotalcostfromastart
nodetoagoalnode.

4. Key Concepts of Uniform Cost Search
1.PriorityQueue:UCSusesapriorityqueuetostorenodes.Thenodewith
thelowestcumulativecostisexpandedfirst.Thisensuresthatthesearch
exploresthemostpromisingpathsfirst.
2.PathCost:Thecostassociatedwithreachingaparticularnodefromthe
startnode.UCScalculatesthecumulativecostfromthestartnodetothe
currentnodeandprioritizesnodeswithlowercosts.
3.Exploration:UCSexploresnodesbyexpandingtheleastcostlynode
first,continuingthisprocessuntilthegoalnodeisreached.Thepathto
thegoalnodeisguaranteedtobetheleastcostlyone.
4.Termination:Thealgorithmterminateswhenthegoalnodeisexpanded,
ensuringthatthefirsttimethegoalnodeisreached,thepathisthe
optimalone.

5. How Does Uniform Cost Search Work?
1.Initialization:UCSstartswiththerootnode.Itisaddedtothepriorityqueuewitha
cumulativecostofzerosincenostepshavebeentakenyet.
2.NodeExpansion:Thenodewiththelowestpathcostisremovedfromthepriority
queue.Thisnodeisthenexpanded,anditsneighborsareexplored.
3.ExploringNeighbors:Foreachneighboroftheexpandednode,thealgorithmcalculates
thetotalcostfromthestartnodetotheneighborthroughthecurrentnode.Ifaneighbor
nodeisnotinthepriorityqueue,itisaddedtothequeuewiththecalculatedcost.Ifthe
neighborisalreadyinthequeuebutalowercostpathtothisneighborisfound,thecost
isupdatedinthequeue.
4.GoalCheck:Afterexpandinganode,thealgorithmchecksifithasreachedthegoal
node.Ifthegoalisreached,thealgorithmreturnsthetotalcosttoreachthisnodeand
thepathtaken.
5.Repetition:Thisprocessrepeatsuntilthepriorityqueueisemptyorthegoalisreached.

6. Algorithm

7. Implementation with
Python

8. Step 1: Import Required Libraries

9. Step 2: Define the Uniform Cost Search
Function

10. Step 3: Define the Path Reconstruction
Function

11. Step 4: Define the Visualization Function

12. Step 5: Define the Graph and Execute UCS

13. Applications of UCS in AI
UniformCostSearchiswidelyapplicableinvariousfieldswithinAI:
1.PathfindinginMaps:Determiningtheshortestroutebetweentwo
locationsonamap,consideringdifferentcostsfordifferentpaths.
2.NetworkRouting:Findingtheleast-costrouteinacommunicationor
datanetwork.
3.PuzzleSolving:Solvingpuzzleswhereeachmovehasacostassociated
withit,suchastheslidingtilespuzzle.
4.ResourceAllocation:Tasksthatinvolvedistributingresourcesefficiently,
wherecostsareassociatedwithdifferentallocationstrategies.

14. Advantages of Uniform Cost Search
•Optimality:UCSisguaranteedtofindtheleastcostpathtothe
goalstateifthecostofeachstepexceedszero.
•Completeness:Thisalgorithmiscomplete;itwillfinda
solutionifoneexists.

15. Challenges with UCS
•SpaceComplexity:ThemaindrawbackofUCSisitsspace
complexity.Thepriorityqueuecangrowsignificantly,
especiallyifmanynodesarebeingexpanded.
•TimeComplexity:Thetimeittakestofindtheleastcostpath
canbeconsiderable,especiallyifthestatespaceislarge.

16. Example

17. Complexity
•�??????�����??????�����??????�??????��=??????(�
�
)
•??????�������??????�����??????�??????��=??????(�
�
∗
/??????
)
Where,
•Branching Factor (b): The average number of successors per state.
•Depth of the Shallowest Goal Node (d): The depth at which the first goal state is found.
•Maximum Path Cost �
∗
The cost of the optimal solution path.
•Where ??????is the smallest step cost greater than zero

18. Conclusion
•UniformCostSearchisapowerfulalgorithminAIforsituations
wherepathshavedifferentcostsandthegoalistominimize
thetotalcost.
•Itsapplicationacrossvariousdomainsshowcasesitsversatility
andeffectiveness.
•However,understandingitscomputationalrequirementsis
crucialforpracticalimplementations,especiallyinscenarios
withlargedatasetsorlimitedcomputationalresources

19. https://github.com/hm18818/AI-with-
Python/blob/main/Uniform%20Cost%20Search%2
0(UCS)%20in%20AI