4
$\begingroup$

What is the uniform-cost search algorithm? How does it work? I would appreciate to see a graphical execution of the algorithm. How does the "frontier" evolve in the case of UCS?

$\endgroup$
2
$\begingroup$

Uniform Cost Search is also called the Cheapest First Search. For an example and entire explanation you can directly go to this link: Udacity - Uniform Cost Search.

In this answer I have explained what a frontier is. To put it in simple words you can describe UCS algorithm as 'expanding the frontier only in the direction which will require the minimum cost to travel from initial point among all possible expansions' i.e. adding a point on the graph (which can be reached from the frontier without going through any other point) which has the shortest route from the initial point. We keep on doing this until a path has explored the goal frontier, this path is the cheapest path from the initial point.

I strongly suggest you check out both the links for examples and better understanding.

NOTE: I have added a YouTube URL in the comments for those who do not want to sign in.

$\endgroup$
  • 1
    $\begingroup$ Nice theoretical explanation what graph search is about, but where is the practical usage of UCS? The only useful application which is possible would be a minimap of 10x10 pixel which contains only of 100 nodes. In such a synthetic example it is possible to use UCS productively, but I've never seen such a small map in a game. Even on the Commodore 64 the problems are much bigger. $\endgroup$ – Manuel Rodriguez Nov 3 '18 at 13:19
  • 2
    $\begingroup$ @ManuelRodriguez that was a really unnecessary downvote, the OP did not ask for usage...only example was required which was provided in the links. $\endgroup$ – DuttaA Nov 3 '18 at 13:37
  • 1
    $\begingroup$ You mean the URL to a website which asks me to sign in with an account? But buy the way, what is behind the paywall can be easily imagined, perhaps the eight queen problem which is not an example but too trivial for everybody who is interested in AI. $\endgroup$ – Manuel Rodriguez Nov 3 '18 at 13:45
  • 2
    $\begingroup$ @ManuelRodriguez it is a free website..it is one of the biggest free and best content providers out there..but since you are more interested in privacy, here is a youtube link youtube.com/watch?v=9vNvrRP0ymw which is probably violating the copyright law by uploading someone elses content. $\endgroup$ – DuttaA Nov 3 '18 at 13:50
  • 1
    $\begingroup$ This link is much better, it explain for the pathplanning problem how the frontline is put forward. It looks a bit like a flood fill algorithm but only for the graph search problem. $\endgroup$ – Manuel Rodriguez Nov 3 '18 at 13:59
-2
$\begingroup$

You are not the first one who is asking what Uniform Cost search (UCS) is. Or to be more precisely, who is asking how it is possible to solve an Artificial Intelligence problem with this search algorithm. The simple answer is: that it's not possible to do any useful thing with UCS, because it has no heuristics. It is a vanilla graph search algorithm, but the term algorithm is perhaps not right, it can be more called a non working piece of code. That means, it is not possible to demonstrate the working of uniform cost search for an example. The only thing what i can provide is to show a non working example.

The idea is maybe that a graph is searched in a linear fashion from top to bottom, similar to another malfunction technique, called Dijkstra' algorithm. How this can be used in real problems for example to control a robot or to find a path in a maze is easy to explain: there no way in doing so. Uniform cost search is some kind of anti-technology which prevents artificial intelligence. That means, if a general game playing agent is using UCS as their main principle we can 100% sure that the agent will do nothing and never ever solve this kind of games.

$\endgroup$
  • 2
    $\begingroup$ The first paragraph is wrong, we can in fact come up with thousands of problems (small toy problems, but still) where UCS does work perfectly fine. The second paragraph is also wrong, even for many complex problems we can actually be 100% sure that the agent will eventually solve them (where that "eventually" typically requires too much memory and time in practice). Even if UCS will (almost) never be the best solution in practice, it is an extremely important, fundamental algorithm to understand well. Beginners will have to understand UCS well before they can move on to other algorithms. $\endgroup$ – Dennis Soemers Nov 3 '18 at 14:11
  • $\begingroup$ I'm with you, that a basic understanding of graph search is important for beginners, because AI has often to do with search. But in case of more complex problems for real AI systems it is possible to show, that UCS will never be successful. The reason is, that it doesn't utilize domain specific knowledge. $\endgroup$ – Manuel Rodriguez Nov 3 '18 at 14:27
  • $\begingroup$ UCS can be viewed as a special case of those graph search algorithms with heuristics you're talking about, where the heuristic function simply returns $0$ everywhere. It can solve precisely the same class of problems, just often being slower due to having a poor heuristic function. So nope, that's wrong. Either way, the question asks for an explanation of the algorithm. Regardless of the inaccuracies in the story, a story about how the algorithm is a poor choice does not provide an answer to the question, it does not explain the algorithm. $\endgroup$ – Dennis Soemers Nov 3 '18 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.