Elements of AI - Search and problem solving

Elements of AI

I.Search and problem solving

Many problems can be phrased as search problems. This requires that we start by formulating the alternative choices and their consequences.

많은 문제가 검색(search) 문제로 표현 될 수 있습니다. 이를 위해서는 대안 선택과 그 결과를 공식화하는 과정이 필요합니다.

Search in practice: getting from A to B

Imagine you’re in a foreign city, at some address (say, a hotel) and want to use public transport to get to another address (a nice restaurant, perhaps). What do you do? If you are like many people, you pull out your smartphone, type in the destination and start following the instructions.

외국의 도시에 있다고 생각해 보세요. 호텔 같은데 있습니다. 그리고 다른 곳으로 (예를 들어 식당같은) 대중교통으로 이동하려고 합니다. 어떻게 하실 겁니까? 다른 사람들 처럼 스마트폰을 꺼내들어 목적지를 입력하고 거기서 안내하는 대로 따라 갈 겁니다. 

This question belongs to the class of search and planning problems. Similar problems need to be solved by self-driving cars, and (perhaps less obviously) AI for playing games. In the game of chess, for example, the difficulty is not so much in getting a piece from A to B as keeping your pieces safe from the opponent.

이 질문은 검색 및 계획에 관한 문제의 범주에 속합니다. 이와 비슷하게 문제를 해결해야 되는 경우는 자율주행차를 예로 들 수 있을 겁니다. 이 자율주행차 문제는 AI 분야도 포함되서 문제를 풀어야 합니다. 예를 들어, 체스 게임에서 어려움은 상대방으로부터 당신의 조각을 안전하게 지키기 위해 A에서 B로 조각을 따내는 것이 아닙니다. 

Often there are many different ways to solve the problem, some of which may be more preferable in terms of time, effort, cost or other criteria. Different search techniques may lead to different solutions, and developing advanced search algorithms is an established research area.

종종 어떤 문제를 해결하는 데에는 여러 가지 방법이 있습니다, 그 중 일부는 시간, 노력, 비용 또는 기타 기준의 관점에서 더 바람직 할 수 있습니다. 서로 다른 검색 기술은 서로 다른 솔루션으로 이어질 수 있습니다. 그리고 고급 검색 알고리즘을 개발하는 것은 이미 확립 된 연구 분야입니다.

We will not focus on the actual search algorithms. Instead, we emphasize the first stage of the problem solving process: defining the choices and their consequences, which is often far from trivial and can require careful thinking. We also need to define what our goal is, or in other words, when we can consider the problem solved. After this has been done, we can look for a sequence of actions that leads from the initial state to the goal.

우리는 실제 검색 알고리즘에 초점을 두지 않을 것입니다. 대신, 우리는 문제 해결 과정의 첫번째 스테이지에 포커스를 맞출겁니다. : 선택을 정의하고 그 선택에 대한 결과는 종종 진부하지 않고 때로는 신중하게 생각할 것을 요구할 수도 있습니다. 우리는 또한 우리의 목표가 무엇인지 정의 할 필요가 있습니다. 즉, 그래야만 나중에 우리는 문제가 해결되었다고 생각할 수 있게 됩니다. 이 작업이 끝나면 초기 상태에서 목표로 이어지는 일련의 동작을 찾을 수 있습니다.

In this chapter, we will discuss two kinds of problems:

이 챕터에서는 아래 두가지 문제에 대해 논의해 볼 겁니다.

• Search and planning in static environments with only one “agent”
• 하나의 "에이전트"만있는 정적 환경에서 검색 및 계획
• Games with two-players (“agents”) competing against each other
• 서로 대결 하는 2 인용 게임 ( 두 "에이전트" 들)

These categories don’t cover all possible real-world scenarios, but they are generic enough to demonstrate the main concepts and techniques.

이 범주는 실제 세상의 모든 시나리오를 다루지는 않지만 주요 개념과 기술을 설명하기에 충분합니다.

Before we address complex search tasks like navigation or playing chess, let us start from a much simplified model in order to build up our understanding of how we can solve problems by AI.

위에서 길찾기나 체스두기처럼 복잡한 검색 작업을 하는 것에 대해 알아봤습니다. 이제 AI로 문제를 해결할 수있는 방법에 대한 이해를 높이기 위해 훨씬 단순화 된 모델부터 시작합시다.

Toy problem: chicken crossing

We’ll start from a simple puzzle to illustrate the ideas. A robot on a rowboat needs to move three pieces of cargo across a river: a fox, a chicken, and a sack of chicken-feed. The fox will eat the chicken if it has the chance, and the chicken will eat the chicken-feed if it has the chance, and neither is a desirable outcome. The robot is capable of keeping the animals from doing harm when it is near them, but only the robot can operate the rowboat and only two of the pieces of cargo can fit on the rowboat together with the robot. How can the robot move all of its cargo to the opposite bank of the river?

그 아이디어를 설명하기 위해 간단한 퍼즐부터 시작하겠습니다. 로보트가 노젓는 배가 있습니다. 강 건너에 여우, 닭 그리고 닭모이가 있는 주머니를 옮겨야 합니다. 여우는 기회가 있다면 닭을 잡아 먹을 것이고 닭은 기회가 있다면 닭모이를 쪼아 먹을 것입니다. 그렇게 되면 안되겠죠. 로봇은 두 동물들이 근처에있을 때 동물이 서로 해를 끼치 지 않도록 막을 수 있습니다. 그 배는 로봇 만이 노를 저을 수 있습니다. 그 보트에는 로보트 이외에 두 개만 더 실을 수 있습니다. 어떻게 로봇이 모든 화물을 피해없이 강 반대편으로 옮길 수 있을까요?

Note

The easy version of the rowboat puzzle

If you have heard this riddle before, you might know that it can be solved even with less space on the boat. That will be an exercise for you after we solve this easier version together.

이 수수께끼를 이전에 들은 적이 있다면 배에 더 작은 공간이 있더라도 해결 할 수 있다는 것을 알고 있을 겁니다. 그 문제는 이 쉬운 버전의 문제를 같이 풀고 난 후 여러분에게 문제로 주어질 것입니다.

We will model the puzzle by noting that five movable things have been identified: the robot, the rowboat, the fox, the chicken, and the chicken-feed. In principle, each of the five can be on either side of the river, but since only the robot can operate the rowboat, the two will always be on the same side. Thus there are four things with two possible positions for each, which makes for sixteen combinations, which we will call states:

우리는 로봇, 보트, 여우, 닭, 닭 사료 등 다섯 가지 움직일 수있는 것들이 있다는 것을 주지하고 퍼즐을 모델링 할 것입니다. 원칙적으로 5 개는 강 양쪽에 있을 수 있지만 로봇 만이 보트를 조작 할 수 있으므로 두 개는 항상 같은쪽에 있습니다. 따라서 각각에 대해 두 가지 가능한 위치를 갖는 네 가지가 있으며, 이는 16 개의 조합을 만들 수 있습니다. 우리는 이 각각의 조합들을 상태 (state) 라고 부를 겁니다.

States of the chicken crossing puzzle

We have given short names to the states, because otherwise it would be cumbersome to talk about them. Now we can say that the starting state is NNNN and the goal state is FFFF, instead of something like “in the starting state, the robot is on the near side, the fox is on the near side, the chicken is on the near side, and also the chicken-feed is on the near side, and in the goal state the robot is on the far side", and so on.

우리는 state라고 명명했습니다. 그렇지 않으면 이야기를 진행할 때 좀 번거롭기 때문입니다. 이 state의 현재 시작 상태는 NNNN이고 목표 상태가 FFFF라고 합시다. "시작 상태에서 로봇은 가까이에 near side 있고, 여우는 가까이에 near side 있고, 닭은 가까이에 near side 있습니다. 또한 닭모이가 가까이에 near side 있고, 목표 상태에서 로봇이 먼쪽에 Far side 있다 "는 식으로 이야기를 진행할 겁니다.

Some of these states are forbidden by the puzzle conditions. For example, in state NFFN (meaning that the robot is on the near side with the chicken-feed but the fox and the chicken are on the far side), the fox will eat the chicken, which we cannot have. Thus we can rule out states NFFN, NFFF, FNNF, FNNN, NNFF, and FFNN (you can check each one if you doubt our reasoning). We are left with the following ten states:

이러한 states 중 일부는 퍼즐 조건에 따라 금지됩니다. 예를 들어, 상태 NFFN (로봇이 닭 사료로 가까이에 있지만 여우와 닭고기가 먼쪽에 있음을 의미)이면 여우는 닭을 잡아 먹을 것입니다. 따라서 우리는 NFFN, NFFF, FNNF, FNNN, NNFF 및 FFNN 상태를 배제 해야 합니다. (의심스러우면 각각을 한번 확인해 보세요.). 우리는 다음과 같은 10 가지 states를 유효한 상황이라고 정할 수 있습니다. :

Next we will figure out which state transitions are possible, meaning simply that as the robot rows the boat with some of the items as cargo, what the resulting state is in each case. It’s best to draw a diagram of the transitions, and since in any transition the first letter alternates between N and F, it is convenient to draw the states starting with N (so the robot is on the near side) in one row and the states starting with F in another row:

다음으로 우리는 어떤 state transition이 가능한지 알아낼 것입니다. 간단히 말해 로봇이 일부 아이템들을 짐으로 보트에 싣고 노를 저어 감으로서 상태 전이 state transition가 생겨나는 겁니다. 이것을 알아보기 쉽게 정리하려면 트랜지션을 다이어그램으로 그리는 것이 가장 좋습니다. 첫번째 운항에서는 그 states를 N으로 즉 로봇이 근처에 있는 것으로 시작하는 것이 편리합니다. 그리고 그 다음 운항에서는  그 상태가 F가 되도록 해서 시작하구요. 

Now let's draw the transitions. We could draw arrows that have a direction so that they point from one node to another, but in this puzzle the transitions are symmetric: if the robot can row from state NNNN to state FNFF, it can equally well row the other way from FNFF to NNNN. Thus it is simpler to draw the transitions simply with lines that don't have a direction. Starting from NNNN, we can go to FNFN, FNFF, FNFN, FFNF, and FFFN:

이제 transition을 그려 보겠습니다. 한 노드에서 다른 노드를 가리키는 방향을 화살표로 그리겠습니다. 이 퍼즐에서는 transitions들은 서로 대칭입니다. 로봇이 NNNN 상태에서 FNFF 상태로 전환하도록 운항할 수 있으면 그 반대의 경우인 FNFF 상태에서 NNNN상태로도 전환할 수 있다는 겁니다. 그렇기 때문에 transitions를 그리는 것은 더 간단합니다. 그냥 화살표 없이 선만 그리면 되기 때문입니다.  NNNN부터 시작해서 FNFN, FNFF, FNFN, FFNF 그리고 FFFN으로 이동할 수 있습니다.

Then we fill in the rest: 그 다음 나머지를 그립니다. :

We have now done quite a bit of work on the puzzle without seeming any closer to the solution, and there is little doubt that you could have solved the whole puzzle already by using your “natural intelligence“. But for more complex problems, where the number of possible solutions grows in the thousands and in the millions, our systematic or mechanical approach will shine since the hard part will be suitable for a simple computer to do. Now that we have formulated the alternative states and transitions between them, the rest becomes a mechanical task: find a path from the initial state NNNN to the final state FFFF.

우리는 정답까지는 아니지만 꽤 일을 진행했습니다. 그런데 조금 의문이 있을겁니다. 여러분은 "natural intelligence 자연 지능"을 사용해서 이미 문제를 다 풀었을 수 있을 겁니다. 이 systematic 하고 mechanical 한 접근법은 좀 더 복잡한 경우에 더 효율적일 겁니다. 예를 들어 경우의 수가 수천, 수백만개가 있을 경우가 그런 경우입니다. 왜냐하면 컴퓨터는 그렇게 경우의 수가 많을 경우 작업하는데 더 자연지능보다 더 우수하기 때문입니다. 수가능한 해결책의 수가 수천에서 수백만으로 증가하는보다 복잡한 문제의 경우, 어려운 부분이 단순한 컴퓨터에 적합하기 때문에 체계적 또는 기계적 접근 방식이 빛날 것입니다. 아뭏든 이제 우리는 대체할 수 있는 states와 transitions 들을 공식화 했습니다. 이제 나머지는 기계적인 작업 mechanical task 입니다. 대체 상태와 전환을 공식화 했으므로 나머지는 기계적인 작업이 됩니다. 초기 상태 NNNN에서 최종 상태 FFFF까지의 경로를 찾는 겁니다.

One such path is colored in the following picture. The path proceeds from NNNN to FFFN (the robot takes the fox and the chicken to the other side), thence to NFNN (the robot takes the chicken back on the starting side) and finally to FFFF (the robot can now move the chicken and the chicken-feed to the other side).

이러한 경로 중 하나는 다음 그림에서 색칠 된 경로도 있습니다. 경로는 NNNN에서 FFFN으로 진행됩니다 (로봇은 여우와 닭을 다른쪽으로 가져갑니다). 그런 다음 NFNN (로봇은 닭을 다시 출발점으로 데려옵니다.)과 FFFF (로봇은 닭모이를 건네고 난 다음 다시 닭을 데리러 와서 싣고 가면 됩니다).

State space, transitions, and costs

To formalize a planning problem, we use concepts such as the state space, transitions, and costs.

planning problem을 공식화하기 위해 우리는 state space, transitions 그리고 costs 같은 개념들을 사용합니다.

Key terminology

The state space

means the set of possible situations. In the chicken-crossing puzzle, the state space consisted of ten allowed states NNNN through to FFFF (but not for example NFFF, which the puzzle rules don´t allow). If the task is to navigate from place A to place B, the state space could be the set of locations defined by their (x,y) coordinates that can be reached from the starting point A. Or we could use a constrained set of locations, for example, different street addresses so that the number of possible states is limited.

The state space은 가능한 상황들의 집합을 의미합니다. chicken-crossing 퍼즐에서 상태 공간은 NNNN에서 FFFF까지의 10 개의 허용 된 상태로 구성됩니다 (예 : NFFF는 퍼즐 규칙에서 허용하지 않음). 작업이 A 지점에서 B 지점으로 이동하는 경우 state space 상태 공간 은 시작 지점 A에서 도달 할 수있는 (x, y) 좌표로 정의 된 위치 집합이 될 수 있습니다. 또는 제한된 위치 집합 , 예를 들어 가능한 거리의 주소가 다를 수 있으므로 가능한 상태의 수가 제한됩니다.

Transitions

are possible moves between one state and another, such as NNNN to FNFN. It is important to note that we only count direct transitions between neighboring states as transitions. A sequence of multiple transitions, for example, from A to C, from C to D, and from D to B (the goal), is a path rather than a single transition.

Transitions 전환은 NNNN에서 FNFN과 같은 하나의 상태와 다른 상태 사이에서 가능한 이동입니다. 인접 states 간 직접 전환 만 전환으로 간주한다는 점에 유의해야합니다. 예를 들어 A에서 C, C에서 D, D에서 B 로의 다중 전환 시퀀스는 단일 전환이 아닌 경로입니다.

Costs

refer to the fact that, oftentimes the different transitions aren´t all alike. They can differ in ways that make some transitions more preferable or cheaper (in a not necessarily monetary sense of the word), and others most costly. We can express this by associating with each transition a certain cost. If the goal is to minimize the total distance traveled, then a natural cost is the geographical distance between states. On the other hand, the goal could actually be to minimize the time instead of the distance, in which case the natural cost would obviously be the time. If all the transitions are equal, then we can ignore the costs.

Costs 비용은 종종 서로 다른 전환들이 모두 비슷하지 않다는 사실을 참조합니다. 그것들은 어떤 전이를 더 바람직하거나 더 싸게 이룰 수 있으며 (반드시 금전적 인 의미는 아님), 다른 것들은 그보다 비용이 더 많이 드는 경우들이 있습니다. 우리는 각 전환과 특정 비용을 연관시킴으로써 이를 표현할 수 있습니다. 목표가 여행 한 총 거리를 최소화하는 것이면 natural cost 자연 비용은 states간의 지리적 거리를 말하게 됩니다. 다른 한편, 목표는 실제로 거리가 아닌 시간을 최소화하는 것이 될 수 있습니다.이 경우 자연 비용은 분명히 시간입니다. 모든 전환이 동일하면 비용을 무시할 수 있습니다.

Exercise 5: A smaller rowboat

In the traditional version of this puzzle the robot can only fit one thing on the boat with it. The state space is still the same, but fewer transitions are possible. Use the state transition diagram below to find a path from the initial state to the final one (we suggest drawing this out to really try).

이 퍼즐의 전통적인 버전에서는 로봇이 보트에 한 가지만 넣을 수 있습니다. The state space 상태 공간은 여전히 동일하지만 더 적은 전환이 가능합니다. 아래의 상태 전이 다이어그램을 사용하여 초기 상태에서 최종 상태로의 경로를 찾으십시오 (실제로 시도하기 위해 이 그림을 그리는 것이 좋습니다).

Your task is now to calculate the length of the shortest path to get from NNNN to FFFF.

이제 여러분은 NNNN에서 FFFF로가는 최단 경로 길이를 계산해야 합니다.

Please type your answer as the number of transitions in the shortest path. (just a single number like "12".) (Hint: Using a paper and a pen might help when doing this exercise.)

최단 경로인 transitions의 수를 답하세요. ( "12"와 같이 단일 숫자로 답하세요.) (힌트 :이 문제를 풀 때 종이와 펜을 사용하면 도움이 될 수 있습니다.)

Exercise 6: The Towers of Hanoi

Let's do another puzzle: the well-known Towers of Hanoi. In our version, the puzzle involves three pegs, and two discs: one large, and one small. (Actually, there can be any number of discs but for the exercise, two is enough to demonstrate the principle.)

또 다른 퍼즐을 풀어 봅시다, 잘 알려진 Towers of Hanoi 를 해보 죠. 우리의 버전에서, 퍼즐은 3 개의 못과 2 개의 디스크로 합니다 : 하나는 크고 하나는 작은 것입니다. (실제적으로 디스크 수는 더 많아도 되지만 연습삼아 하기에는 두개만 사용해도 이 원리를 입증하는데는 충분합니다.

In the initial state, both discs are stacked in the first (leftmost) peg. The goal is to move the discs to the third peg. You can move one disc at a time, from any peg to another, as long as there is no other disc on top of it. It is not allowed to put a larger disc on top of a smaller disc.

초기 상태에서 두 디스크는 첫 번째 (대부분 왼쪽) peg 페그에 쌓입니다. 목표는 디스크를 세 번째 못으로 이동하는 것입니다. 여러분은 한번에 하나의 디스크를 다른 페그로 옮길 수 있습니다. 다만 그 위에 다른 디스크가 없는 경우에만 가능하겠죠. 작은 디스크 위에 큰 디스크가 올라가면 안 됩니다. 

This picture shows the initial state and the goal state. There are also seven other states so that the total number of possible states is nine: three ways to place the large disc and for each of them, three ways to place the small disc.

이 그림은 초기 상태와 목표 상태를 보여줍니다. 이 이외에 7개의 다른 가능한 상태들이 있습니다. 그러므로 총 9개의 가능한 상태들이 있습니다. large 디스크를 배치하는 세 가지 방법과 각각에 대해 작은 디스크를 배치하는 세 가지 방법이 있습니다.

Your task: Draw the state diagram. The diagram should include all the nine possible states in the game, connected by lines that show the possible transitions. The picture below shows the overall structure of the state diagram and the positions of the first three states. It shows that from the starting state (at the top corner), you can move to two other states by moving the small disc. Complete the state diagram by placing the remaining states in the correct places. Note that the transitions are again symmetric and you can also move sideways (left or right) or up in the diagram.

과제 : state diagram 상태 다이어그램을 그리세요. 다이어그램에는 이 게임에서 가능한 9 가지 상태가 모두 포함되어야하며 possible transitions 전환이 가능함을 보여주는 선으로 연결됩니다. 아래 그림은 state diagram의 전반적인 구조를 보여줍니다. 이 첫 세 상태의 포지션을 보여줍니다. 그 다음은 시작 상태 에서 작은 디스크를 움직여 다른 두 상태로 이동할 수 있음을 보여줍니다. 나머지 상태를 올바른 위치에 배치하여 상태 다이어그램을 완성하십시오. 이 전환들은 서로 다시 대칭이므로 다이어그램에서 옆으로 (왼쪽 또는 오른쪽) 또는 위로 이동할 수도 있습니다.

After solving the task using pen and paper, enter your solution by choosing which state belongs to which node in the diagram. (Hint: Each state belongs to exactly one node.)

펜과 종이를 사용하여 작업을 해결 한 후 다이어그램에서 어떤 state가 어느 노드에 속해 있는지 선택하여 여러분의 답을 입력하세요. (힌트 : 각 상태는 정확하게 하나의 노드에 속합니다.)

Choose for each node (1–6) in the above diagram the correct state A—F from below.

위 그림에서 각 노드 (1-6)에 대해 아래에서 올바른 A-F state를 선택하십시오.