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?
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.
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.