Bab 3 Solving Problem by Searching Problem Solving Agent • •
Simple Reflex agents are unable to plan ahead • Their action are determined only by current percept • No knowledge of what their action nor what is the goal Typical tasks yang termasuk dalam simple reflex agents antara lain: • Get to location x • Lay out chip • Clean rooms in house • Solve puzzle
•
Pada task diatas umumnya mendapatkan informasi tentang Goal yang harus dicapai dengan suatu preferences tertentu. Namun untuk mencapai Goal yang ditentukan, seringkali suatu agent harus melakukan suatu sequence action antara [immediate actions] yang harus dipilih dari berbagai alternatives yang ada. Pada kenyataannya, Agent tidak memiliki knowledge untuk menentukan alternative manakah yang terbaik. Pada situasi ini, suatu agent harus melalui suatu proses untuk menentukan sequence of actions mana yang terbaik untuk mencapai Goal yang ditentukan dan process ini disebut search.
•
Before an agent can start searching for solution, it must formulate a goal and then use the goal to formulate the problem [problem formulation] 1. Goal formulation based on current situation, is the first step in problem solving. 2. Problem formulation is the process of deciding which actions and states to consider, and follows goal formulation.
•
The environment of the problem is represented by a state space and a path through the state space from the initial state to a goal state is a solution. Secara general input dari suatu search adalah Goal, Utility yang dibutuhkan, states dan actions sedangkan outputnya adalah sequence of action (from current state, through other states) menuju goal.
• •
Problem umumnya didefinisikan, dalam 4 bagian penting yaitu: 1. An initial state 2. A set of operators 3. A goal test function 4. A “path cost” function.
•
Problem Solving Agent adalah salah satu dari goal-based agent dan merupakan bentuk terbatas dari suatu general agent
Problem yang dihadapi dapat dibedakan atas beberapa tipe problem [problem type] yaitu: 1. Deterministic, accessible merupakan single-state problem 2. Deterministic, inaccessible merupakan multi-state problem 3. Nondeterministic, inaccessible merupakan contingency problem 4. Unknown state space merupakan exploration problem (online) Contingency problem umumnya diselesaikan dengan bantuan sensors during eksekusi dan menghasilkan suatu “tree solution” atau suatu policy. Dalam pelaksanaannya proses penentuan solusi dilakukan secara interleave antara search dan eksekusi. [Lihat catatan tambahan di lampiran bab ini]
Saudara sedang berlibur di Romania, dan saat ini ada di kota Arad. Jadwal penerbangan saudara untuk pulang adalah besok dari kota Bucharest. Maka: Goal : Berada di Bucharest Problem : states : various cities Operators : drive between cities Solution : sequence of cities, misalnya Arad, Sibiu, Fagaras, Bucharest.
Penentuan state space Real world is absurdly complex
state space must be abstracted for problem solving
(Abstract) state = set of real states (Abstract) Operators = complex combination of real actions Misalnya: dari Arad Zerind represents a complex set of possible routes, detours, rest stops, dll. Untuk menjamin realizability, any real state in Arad must get to sama real state is Zerind. (Abstract) Solution = set of real paths that are solutions in the real world Remember: Setiap abstract action harus “easier” than original problem. Algoritma umum dari suatu general search adalah sbb: --------------------------------------------------------------------------------------------------------------------function GENERAL-SEARCH (problem, QUEUING-FN) returns a solution or failure nodes MAKE-QUEUE( MAKE-NODE (INITIAL_STATE [problem])) loop do if nodes is empty then return failure // no candidates for expansion nodes REMOVE-FRONT(nodes) // choose a leaf node for expansion depend on strategy if GOAL-TEST[problem] applied to STATE(node) succeeds then return node else nodes QUEUING-FN(nodes, EXPAND(node, OPERATORS[problem])) end
---------------------------------------------------------------------------------------------------------------------Basic idea dari suatu search algorithms adalah expanding states atau “simulated exploration of state space by generating successors of already-explored states”. Algoritma dari suatu simple problem solving agent dapat dilihat berikut ini: --------------------------------------------------------------------------------------------------------------
function SIMPLE_PROBLEM_SOLVING_AGENT (p) returns an action input: p, a percept static: a, an action sequence, innitially empty state, some description of current world state g, a goal, innitially null problem, a problem formulation state UPDATE_STATE (state, p) if a is empty then g FORMULATE_GOAL (state) problem FORMULATE_PROBLEM (state, g) a SEARCH (problem) action RECOMMENDATION (a, state) a REMAINDER (a, state) return action
-----------------------------------------------------------------------------------------Algoritma diatas dianggap sebagai suatu offline problem solving atau online problem solving yang melibatkan action tanpa “complete knowledge” dari problem dan kemungkinan solution yang ada.
Uniformed Search Strategies Uniformed search strategies use only the information available in the problem definition. This strategies is implemented in: • Breadth First Search (BFS) • Uniform Cost Search • Depth First Search (DFS) • Depth Limited Search • Iterative Deepening Search Hal hal yang harus diperhatikan dalam implementasi suatu algoritma search antara lain: Suatu state adalah suatu representasi dari suatu physical configuration atau suatu snapshot of event, jadi states tidak memiliki parents, children, dept maupun path cost sedangkan suatu node adalah suatu data struktur yang merupakan bagian dari suatu search tree termasuk parent node, children nodes yang memiliki depth dan path cost tertentu.
Fungsi EXPAND akan meng „create“suatu new nodes, dan dengan menggunakan OPERATORS atau SUCCESSORFn dari problem untuk meng “create” state yang berkaitan. Search strategy pada dasarnya ditentukan oleh cara pemilihan urutan node yang akan di “expand”, dan keberhasilan strategy tersebut dievaluasi berdasarkan 4 kriteria berikut ini: 1. Completeness, apakah strategy tersebut selalu menemukan solusi jika solusinya ada? 2. time complexity, ditentukan berdasarkan jumlah node yang di generate dan di expand untuk memperoleh solusi 3. space complexity, yaitu jumlah maksimum nodes yang disimpan di memory selama proses pencarian solusi 4. optimality, apakah strategy tersebut selalu mendapatkan solusi yang terbaik atau least-cost solution Time and space complexity diukur berdasarkan besaran: 1. b = maksimum branching factor dari search tree 2. d = depth dari least cost solution 3. m = maksimum depth dari state space ( dapat bernilai tak terhingga). Untuk ke lima metoda Uninformed search strategies diatas kita mengambil contoh soal Romania diatas dimana jarak antar kota dapat dilihat pada tabel
Breadth First Search (BFS) • • •
Expand shallowest unexpanded node Space needed is the big problem in BFS Implementation: QUEUING-FN = put successors at the end of the queue.
Karakteristik dari BFS: Complete Time Space Optimal
: Yes (if branching factor of the tree b is finite) 2 3 d : 1 + b + b + b +…+ b (exponential in d.) d : O (b ) because we keep every node in memory. : Yes (if cost = 1 per step but not optimal in general)
Space akan menjadi big problem pada BFS, bayangkan saudara akan membutuhkan memory sebesar 86 Gbyte untuk 24 jam proses dengan kecepatan 1 Mbyte/det
Uniform Cost Search • •
Pada Uniform Cost Search kita akan expand “Least-cost unexpanded node”. Implementation: QUEUING-FN = insert in order of increasing path cost.
Karakteristik dari Uniform Cost Search Complete Time Space Optimal
: Yes (if step cost : # of nodes with g : # of nodes with g : Yes
.) cost of optimal solution ) cost of optimal solution )
Depth First Search (DFS) • • • • • • • •
DFS always expands one of the nodes at the deepest level of the tree Implementation: QUEUING-FN = insert the successors in front of the queue DFS can perform infinite cyclic excursions so, DFS need a finite, non-cyclic search space Or repeated state checking Only when the search hits a dead end ( a non-goal node with no expansion), go back and expand nodes at shallower level DFS can be implemented by general search with queuing function that always put the newly generated states in front of the queue. (QUEUING-FN = insert the successors in front of the queue) The memory requirement is O(bm) where b is branching factor and m = maximum depth because DFS only needs storage for bm nodes. m Time complexity is O(b ), so DFS usually faster than BFS The drawback of DFS, it can get stuck going down the wrong path (problem for deep and infinite search tree) and it can be infinite loop
Depth limited Search • •
Depth Limited Search is used to avoid the problem in DFS by imposing a cutoff on the maximum depth of a path. The cutoff can be implemented using: • A special depth limited search algorithm. • A general search algorithm with operator that keep track of the depth.
Note: There are 20 cities on the map of Romania. So if there is a solution, the longest search length is 19. The depth cut of operator is “ if you are in city A, and have traveled a path less than 19 steps, then generate a new state with a path length that is one greater”. It is guarantee to get the solution (if one exist) but not the shortest path solution).
Iterative Deepening Sama dengan Depth Limited search hanya depth d secara iterative bertambah mulai dari d = 1 sampai maksimum
Contoh soal Dari gambar dibawah ini, S adalah start state dan G adalah Goal state
Ketika meletakan child nodes hasil ekspansi suatu node, maka child node diletakkan menurut alphabetical order, misalkan pula kita tidak pernah men “generate” child nodes” yang pernah menjadi ancestors dari current node pada search tree. Maka: urutan BFS dalam meng “expand” node adalah
SABBDACECEE
G
urutan DFS dalam meng “expand” node adalah
SABCHED
G
urutan Iterative Deepening dalam meng “expand” node adalah
SSABSABD
G
Note that when we are searching with a depth limit of d we do not expand nodes at that level but we do test them to see if they are goal states. For example, the diagram below shows the search tree on the third iteration (depth limit = 3). For this tree we expand nodes S A B D. Nodes C, E, E and G are tested to see if they are goal states but they are not expanded.
Alternatively, if we consider nodes at the depth limit as \expanded" (i.e. in the above example C, E, and G) then our solution is:
SABSABDBACESABCEDE
G
