Heuristic Search ÀÇ ¿ª»ç

 

depth first search (µÇÃßÀû Ž»ö) À» °³¼±ÇÒ ¼ö ÀÖ´Â ´Ù¾çÇÑ ¹æ¹ýµé·Î Á¾¼Ó °ü°è¿¡ ÀÇÇÑ µÇÃßÀû (dependency directed backtracking) [Richard Stallman  & Gerald Sussman 1977. Forward Reasoning and Dependency Directed Backtracking in a ...], µÇµµ¾à (backjumping) [Gaschnig 1979], µ¿Àû µÇÃßÀû (dynamic backtracking) [Matthew Ginsberg 1993. Dynamic Backtracking] µîÀÌ ÀÖ´Ù. ¸¶Áö¸· ³í¹®¿¡¼­´Â ÀÌ·¯ÇÑ ¹æ¹ýµéÀ» ºñ±³ÇÏ°í µ¿Àû µÇÃßÀû ¹æ¹ýÀÇ ÀåÁ¡À» ¼³¸íÇÏ°í ÀÖ´Ù. ÀÌ·¯ÇÑ Çâ»óµÈ µÇÃßÀû ±â¹ýµéÀº ÀϹÝÀûÀ¸·Î Á¦¾àÁ¶°Ç ÃæÁ· (constraint satisfaction) ¹®Á¦¿¡ ¸¹ÀÌ Àû¿ëµÈ´Ù.

heuristic search ´Â µÎ Á¾·ùÀÇ °è»êÀ» ¼öÇàÇÑ´Ù. ù°·Î, ½ÇÁ¦·Î ³ëµå¸¦ È®ÀåÇÏ°í °æ·Î ÀÚü¸¦ »ý¼ºÇÏ´Â °´Ã¼ ·¹º§ (object level) ÀÇ °è»êÀÌ ÀÖ´Ù. µÑ°·Î, ´ÙÀ½¿¡ ¾î´À ³ëµå¸¦ È®ÀåÇÒ °ÍÀÎÁö¸¦ °áÁ¤ÇÏ´Â ¸ÞŸ ·¹º§ (meta level) ÀÇ °è»êÀÌ ÀÖ´Ù. °´Ã¼ ·¹º§Àº ½Ç¼¼°è¿¡¼­ÀÇ ¹°¸®ÀûÀÎ Çൿ¿¡ °üÇÑ °ÍÀÌ°í, ¸ÞŸ ·¹º§Àº ±×·¡ÇÁ¿¡¼­ÀÇ °è»ê¿¡ °üÇÑ °ÍÀÌ´Ù. °´Ã¼ ·¹º§°ú ¸ÞŸ ·¹º§ÀÇ ±¸ºÐÀº AI ¿¡¼­ ÀÚÁÖ µîÀåÇÑ´Ù. À̵éÀº [Stuart Russell & Wefald 1991. Do the Right Thing] ¿¡ öÀúÇÏ°Ô ³íÀǵǾî ÀÖÀ¸¸ç, °èȹ, Çൿ ±×¸®°í ÇнÀ¿¡¼­´Â ¼³¸íÇÒ ´ÜÃàµÈ (abbreviated) Ž»ö ¹æ¹ý¿¡ À־ ƯÈ÷ Áß¿äÇÑ ¿ªÇÒÀ» ¼öÇàÇÑ´Ù.

ŸÀÏ ¸ÂÃ߱⠹®Á¦´Â ¸¹Àº AI ¿¬±¸Àڵ鿡 ÀÇÇØ ÈÞ¸®½ºÆ½ Ž»ö ¹æ¹ýÀ» ½ÃÇèÇϱâ À§ÇÑ Å×½ºÆ®º£µå (testbed) ·Î »ç¿ëµÇ¾î ¿Ô´Ù. [Doran & Michie 1966. Experiments with the Graph Traverse Program] ÀÇ ÃÊ±â ³í¹®ÀÌ 8 ÆÛÁñÀ» »ç¿ëÇß°í, ±× ÀÌÈÄ·Î »ç¶÷µéÀÌ ±×·¡ÇÁ¿¡¼­ °æ·Î¸¦ ã´Â °úÁ¤¿¡ Æò°¡ ÇÔ¼ö¸¦ »ç¿ëÇϱ⠽ÃÀÛÇß´Ù.

1990 ³â¿¡ Korf ´Â "IDA* ·Î 15 ÆÛÁñÀº Ç® ¼ö ÀÖÁö¸¸ ±× ÀÌ»óÀÇ ÆÛÁñ (24 ÆÛÁñ µî) Àº ÇöÀçÀÇ ÄÄÇ»ÅͷΠó¸®ÇÒ ¼ö ¾ø´Ù" °í ÇÏ¿´´Ù [Korf 1990, Realtime Heuristic search]. ÇÏÁö¸¸ ´õ °­·ÂÇÑ ÄÄÇ»ÅÍ (ÃÊ´ç ¹é¸¸ °³ÀÇ ³ëµå¸¦ »ý¼ºÇÒ ¼ö ÀÖ´Â Sun Ultra Sparc ¿öÅ©½ºÅ×À̼Ç) ¿Í ´õ °­·ÂÇÑ (ÀÚµ¿ÀûÀ¸·Î ã¾ÆÁø) ÈÞ¸®½ºÆ½À» »ç¿ëÇÏ¿© [Richard Korf & Taylor 1996. Optimal Solution to 24 puzzles] ´Â ¹«ÀÛÀ§·Î ¸¸µé¾î³½ ´äÀÌ ÀÖ´Â 24 ÆÛÁñ ¹®Á¦¿¡ ´ëÇÑ ÃÖÀûÇظ¦ 2 ½Ã°£ 15 ºÐ¿¡¼­ 1 °³¿ù »çÀÌÀÇ ½Ã°£¿¡ ã¾Æ³¾ ¼ö ÀÖ¾ú´Ù. [Richard Korf 1997. Optimal Solution to Rubik's Cube Using Pattern Databases] ´Â IDA* ¸¦ 3 × 3 × 3 ·çºò½º Å¥ºê (Rubik's Cube) ÆÛÁñÀÇ ÃÖÀû Çظ¦ ã´Â µ¥µµ Àû¿ëÇÏ¿´´Ù.

Ž»ö ±â¹ýµéÀ» ½ÃÇèÇÏ°í °³¼±Çϱâ À§ÇÏ¿© ÆÛÁñµéÀÌ À¯¿ëÇÏ°Ô »ç¿ëµÇ¾î ¿ÔÁö¸¸, A* ¿Í ±âŸ ÈÞ¸®½ºÆ½ Ž»ö ¹æ¹ýµéÀº ¸¹Àº ½ÇÁ¦ ¹®Á¦¿¡µµ ¼º°øÀûÀ¸·Î Àû¿ëµÇ¾î ¿Ô´Ù. ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦ ã±â À§ÇÑ ¿ÏÈ­µÈ ¸ðµ¨¿¡ ´ëÇÏ¿© ´õ ÀÚ¼¼ÇÑ ³»¿ëÀº [Mostow & Prieditis 1989, Prieditis 1993] ¿¡ ³ª¿Í ÀÖ´Ù. [Pohl 1973] Àº ÀÇ ÈÞ¸®½ºÆ½ ¿ä¼Ò¿¡ ´ëÇÑ °¡ÁßÄ¡¸¦ Á¶Á¤ÇÏ´Â ½ÇÇèÀ» ¼öÇàÇÏ¿´´Ù.

ÈÞ¸®½ºÆ½ Ž»ö¿¡ ´ëÇÑ °¡Àå °íÀüÀûÀΠåÀº [Judea Pearl 1984. Heuristics Intelligent Search Strategies...] ÀÌ´Ù. [Laveen N. Kanal & Kumar 1988. Search in AI] Àº Ž»ö¿¡ °üÇÑ ³í¹®µéÀ» ¸ð¾Æ³õÀº Ã¥ÀÌ´Ù. ÀÌ Ã¥ÀÇ Ã¹ ¹ø° ³í¹®Àº AI ¿Í OR (operations research) ¿¬±¸Àڵ鿡 ÀÇÇØ °¢°¢ µ¶¸³ÀûÀ¸·Î °³¹ßµÈ Ž»ö ¹æ¹ýµéÀ» Çϳª·Î ÅëÀϽÃų °ÍÀ» Á¦¾ÈÇÏ°í ÀÖ´Ù.

 planning

°¨Áö/°èȹ/Çൿ Áֱ⠴ Agre ¿Í Chapman ÀÌ ¸»ÇÑ ÀÎÅ͸®ºê °èȹ (interleaved planning) ÀÇ ÇÑ ¿¹ÀÌ´Ù [Philip Agre & Chapman 1990 What are plans for?]. À̵éÀº À̵éÀÌ Á¦¾ÈÇÑ ÁïÈï Çൿ (improvisation) °í ÀÎÅ͸®ºê °èȹÀ» ´ëºñÇÏ¿© ¼³¸íÇÏ¿´´Ù. [Agre & Chapman 1990, p.30] ¿¡ ´ÙÀ½°ú °°Àº ¸»ÀÌ ³ª¿Í ÀÖ´Ù. ÀÎÅ͸®ºê °èȹ°ú ÁïÈï ÇൿÀº ¹®Á¦¿¡ ´ëÇÑ ÀÌÇØÀÇ Ãø¸é¿¡¼­ ´Ù¸£´Ù. ÀÎÅ͸®ºê °èȹ¿¡¼­´Â °èȹ¿¡ µû¶ó ÁøÇàµÇ´Â °ÍÀÌ Á¤»óÀûÀÌ°í, ¹®Á¦°¡ ÀϾ´Â °ÍÀº ¿¹¿ÜÀûÀÎ Çö»óÀÌ´Ù. ÁïÈï Çൿ¿¡¼­´Â ¸ðµç ÀÏÀÌ °èȹ¿¡ µû¶ó ÁøÇàµÇÁö ¾Ê´Â´Ù°í °¡Á¤ÇÑ´Ù. µû¶ó¼­, ¿¡ÀÌÀüÆ®´Â Áö¼ÓÀûÀ¸·Î »õ·Î¿î ÆÇ´ÜÀ» ³»·Á¾ß¸¸ ÇÑ´Ù.

±×·¯³ª ÀÎ½Ä ¹× ÀÛµ¿ ½Ã½ºÅÛ¿¡¼­ ¹®Á¦°¡ ¹ß»ýÇÏ´Â »óȲÀÌ ¿¹¿ÜÀûÀÎ °ÍÀÌ µÇµµ·Ï (ÁÖ¾îÁø ÀÓ¹«¿Í ȯ°æÀ» °í·ÁÇÏ¿©) ¼³°èÇÏ´Â °ÍÀº ´ç¿¬È÷ ¼³°èÀÚÀÇ ÀÓ¹«°¡ ¾Æ´Ñ°¡? T-R Æ®¸® [Nils J.Nilsson 1994] ¿Í °°Àº ÇüÅ¿¡¼­ÀÇ °èȹÀº ¿¹¿ÜÀûÀÎ ¹®Á¦¿¡ ´ëÇØ »ó´çÈ÷ °­°ÇÇÏ´Ù. ÀÎÅ͸®ºê °èȹ°ú ½ÇÇà¿¡ ´ëÇÑ ´õ ÀÚ¼¼ÇÑ ³»¿ëÀº [Stentz 1995, Stentz & Hebert 1995, Nourbakhsh 1977] ¿¡ ³ª¿Í ÀÖ´Ù.

¼¶À» ÅëÇÑ Å½»ö¿¡ °üÇؼ­´Â [Chakrabarti, Ghose, & DeSarkar 1986] À», °èÃþÀû °èȹ¿¡ ´ëÇÑ ¸ðµ¨°ú ºÐ¼®¿¡ ´ëÇؼ­´Â [Richard Korf 1987, Bacchus & Yang 1992] ¸¦ ÂüÁ¶Ç϶ó. [Stefik 1995, pp.259-280] ¿¡´Â °èÃþÀû °èȹ¿¡ ´ëÇÑ ¸íÄèÇÑ ¼³¸íÀÌ ³ª¿Í ÀÖ´Ù.

½Ã°è Á¦ÇÑ Å½»ö¿¡¼­´Â ½Ã°è¸¦ ÁöÁ¤ÇØ¾ß ÇÑ´Ù. ÀÌ·¯ÇÑ °áÁ¤À» Çϱâ À§Çؼ­´Â Ãß°¡ÀûÀÎ °è»êÀÇ °¡Ä¡¿Í ÀÌ¹Ì ¼öÇàµÈ °è»ê¿¡ ÀÇÇØ ÃßõµÇ´Â ÇൿÀÇ °¡Ä¡ »çÀÌÀÇ ÀýÃæÀ» °í·ÁÇØ¾ß ÇÑ´Ù. ÀÌ ÀýÃæÀº Çൿ Áö¿¬ÀÇ ºñ¿ë¿¡ ÀÇÇØ ¿µÇâÀ» ¹Þ´Â´Ù. Ãß°¡ÀûÀÎ °è»ê°ú Áï°¢ÀûÀÎ ÇൿÀÇ »ó´ëÀûÀÎ °¡Ä¡¸¦ Æò°¡ÇÏ´Â °ÍÀº ¸ÞŸ ·¹º§ °è»êÀÇ ÇÑ ¿¹ÀÌ´Ù. ÀÌ ÁÖÁ¦¿¡ °üÇؼ­´Â [Russell & Wefald 1991, 5Àå] ¿¡¼­ ÀÚ¼¼È÷ ´Ù·ç°í ÀÖ´Ù. À̵éÀÇ DTA* ¾Ë°í¸®ÁòÀº ÀÌ·± ÁÖÁ¦¿¡ ´ëÇÑ ¾ÆÀ̵ð¾î¸¦ ±¸ÇöÇÑ °ÍÀÌ´Ù.

[Lee & Mahajan 1988] Àº Æò°¡ ÇÔ¼öÀÇ ÇнÀ ¹æ¹ýÀ» ±â¼úÇÏ°í ÀÖ´Ù. Áö¿¬µÈ º¸»ó (delayed reinforcement) °ú ½Ã°£ Â÷ÀÌ (temporal difference) ÇнÀ ¹æ¹ýÀº È®·üÀûÀÎ µ¿Àû ÇÁ·Î±×·¡¹Ö (stochastic dynamic programming) °ú ¹ÐÁ¢ÇÑ °ü·ÃÀÌ ÀÖ´Ù. ¿©±â¿¡ ´ëÇؼ­´Â [Barto, Gradtke, & Singh 1995, Ross 1988] À» Âü°íÇ϶ó. º¸»óÀ» ±â¹ÝÀ¸·Î ÇÏ¿© Çൿ Á¤Ã¥À» ÇнÀÇÏ´Â ·Îº¿ ½Ã½ºÅÛÀÇ ¿¹µéÀº [Mahadevan & Connell 1992] ¿Í [Connell & Mahadevan 1993b] ¿¡ ³ª¿Í ÀÖ´Ù. [Moore & Atkeson 1993] ¿¡´Â ½ÇÁ¦ÀûÀÎ ½Ã½ºÅÛÀ» Á¦¾îÇϱâ À§ÇÑ È¿À²ÀûÀÎ ±â¾ï±â¹Ý (memory-based) º¸»ó ¹æ¹ýÀÌ Á¦½ÃµÇ¾î ÀÖ´Ù. [Montague, et al. 1995] ´Â °­È­ ÇнÀÀ» ±â¹ÝÀ¸·Î ²Ü¹úÀÌ ²ÜÀ» ã¾Æ´Ù´Ï´Â Çൿ¿¡ ´ëÇÑ ¸ðµ¨À» Á¦½ÃÇÏ¿´°í, [Schultz, Dayan, & Montague 1997] Àº ½Ã°£ Â÷ÀÌ ÇнÀ ¹æ½ÄÀÌ ¿µÀå·ùÀÇ ½Å°æ°è¿¡ ¾î¶»°Ô ±¸ÇöµÇ¾î ÀÖ´ÂÁö¸¦ ¼³¸íÇÏ°í ÀÖ´Ù.

 °ÔÀÓ

ÆÛÁñó·³ °ÔÀӵ鵵 AI ±â¹ýµéÀ» ´Ùµë°í ½ÃÇèÇÏ´Â µ¥ ¸Å¿ì Áß¿äÇÑ ¿ªÇÒÀ» ÇØ¿Ô´Ù. ¿¹¸¦ µé¾î [Russell & Wefald 1991, 4 Àå] ´Â ¾ËÆÄ º£Å¸º¸´Ù È¿°úÀûÀÎ ¹æ¹ýÀ¸·Î Ž»öÆ®¸®¸¦ ÁÙÀ̱â À§ÇØ (°è¼ÓµÇ´Â Ž»öÀÇ ±â´ë°ªÀ» ÀÌ¿ëÇÏ¿©) ¸ÞŸ ·¹º§ °è»êÀ» ¼öÇàÇÏ´Â °ÔÀÓÆ®¸® ¾Ë°í¸®Áò (MGSS* ¿Í MGSS2) À» Á¦¾ÈÇÏ¿´´Ù. Berliner ÀÇ B* ¾Ë°í¸®Áòµµ ±¸°£ ÇÑ°è (interval bound) [Berliner 1979] ¸¦ »ç¿ëÇÏ¿© º¸´Ù È¿°úÀûÀÎ Àý´ÜÀ» ÇÑ´Ù. [Korf 1991] Àº ¾ËÆÄ º£Å¸ ¹æ¹ýÀ» ¿©·¯ ¸íÀÌ ÇÏ´Â °ÔÀÓ¿¡ Àû¿ëÇϵµ·Ï È®ÀåÇÏ¿´´Ù.

¼öÄ¡ Æò°¡ ÇÔ¼ö¸¦ »ç¿ëÇÏ´Â ´ë½Å¿¡, °ÔÀÓ¿¡ ´ëÇÑ ÀϺΠ¿¬±¸¿¡¼­´Â ÇϳªÀÇ »óȲÀÌ ´Ù¸¥ »óȲ¿¡ ºñÇØ ´õ ÁÁÀºÁö (better than) ȤÀº ´õ ³ª»ÛÁö (worse than) ¸¦ ÆÇ´ÜÇÏ´Â µ¥ ÆÐÅÏÀÎ½Ä (pattern recognition) ±â¹ýÀ» »ç¿ëÇÏ¿´´Ù. ÀÌ·¯ÇÑ ±â¹ýÀº ü½ºÀÇ °ÔÀÓ ¸¶Áö¸· ºÎºÐÀ» ¼öÇàÇÏ´Â ÇÁ·Î±×·¥¿¡ »ç¿ëµÇ¾ú´Ù [Huberman 1968, Bratko & Michie 1980].

°ÔÀÓ¿¡ ´ëÇÑ °¡Àå ¼º°øÀûÀÎ Ãʱ⠾÷ÀûÀº üĿ (Checker) °ÔÀÓ¿¡¼­ÀÇ ±â°è ÇнÀ (machine learning) ¹æ¹ýÀ» °³¹ßÇÑ Arthur Samuel ÀÇ ¿¬±¸ÀÌ´Ù [Samuel 1967 Some Studies in Machine Learning Using the Game of Checkers]. Samuel ÀÇ Ã¼Ä¿ ÇÁ·Î±×·¥Àº èÇǾ𿡠°¡±î¿î ¼öÁØÀ¸·Î °ÔÀÓÀ» ¼öÇàÇÏ¿´´Ù. ÇöÀç´Â University of Alberta ¿¡ ÀÖ´Â Jonathan Schaeffer ÀÇ CHINOOK ÇÁ·Î±×·¥ [Schaeffer et al.1992 A World Championship Caliber Checkers Program, Schaeffer 1997] ÀÌ ¼¼°è üĿ èÇǾðÀ¸·Î ¾Ë·ÁÁ® ÀÖ´Ù. 1997³â¿¡´Â IBM ÀÇ ÇÁ·Î±×·¥ÀÎ DEEP BLUE °¡ èÇǾð ŸÀÌƲÀü¿¡¼­ ¼¼°è ü½º èÇǾðÀÎ Garry Kasparov ¸¦ ÀÌ°å´Ù.

[Monty Newborn 1996 Computer Chess Comes of Age] Àº ÄÄÇ»ÅÍ Ã¼½º¿¡ °üÇÑ Ã¥À¸·Î¼­, 1996³â¿¡ DEEP BLUE °¡ Garry Kasparov ¿¡°Ô ÆÐÇÒ ¶§±îÁöÀÇ ¿ª»ç¸¦ ¿­°ÅÇÑ °ÍÀÌ´Ù. ÀÌ Ã¥¿¡ ´ëÇÑ ¼­Æò°ú AI ¸¦ À§ÇÑ ¿¬±¸¿ëÀ¸·Î¼­ÀÇ Ã¼½ºÀÇ ¿ªÇÒ¿¡ ´ëÇÑ ¼³¸íÀº [John McCarthy 1997 AI as Sport] À» ÂüÁ¶Ç϶ó. McCarthy ´Â ü½º ÇÁ·Î±×·¥ÀÌ Á»´õ Àΰ£°ú ºñ½ÁÇÑ Ãß·Ð ¹æ¹ýÀ» »ç¿ëÇÑ´Ù¸é ´õ ÀûÀº Ž»öÀ¸·Îµµ ´õ ³ªÀº ¼º´ÉÀ» º¸ÀÏ °ÍÀ̶ó°í ÇÏ¿´´Ù. [Donald Michie 1966 Game Playing and Game Learning Automata] ´Â ±â´ë°ª ÃÖ´ëÈ­ (expectimax) ¶ó´Â ¸»À» ¸¸µé°í ÀÌ ±â¹ý¿¡ ´ëÇÑ ½ÇÇèÀ» ¼öÇàÇÏ¿´´Ù.

[Lee & Mahajan 1988] Àº °­È­ ÇнÀ (reinforcement learning) ¹æ¹ýÀ» ¿À¼¿·Î (Othello) °ÔÀÓ¿¡ Àû¿ëÇÏ¿´À¸¸ç, [Schraudolph, Dayan, & Sejnowski 1994] ´Â ½Ã°£Â÷ÀÌ (temporal difference) ±â¹ýÀ» ¹ÙµÏ¿¡ Àû¿ëÇÏ¿´´Ù. ÀϹÝÀûÀÎ °ÔÀÓ Å½»ö ¹æ¹ý¿¡ ´ëÇØ ´õ ¾Ë°í ½Í´Ù¸é [Judea Pearl 1984, Heuristics Intelligent Search Strategies... 9 Àå] À» ÂüÁ¶Ç϶ó.