Ebben a fejezetben látni fogjuk, hogy az állapottérrel kapcsolatos információ segítségével az algoritmusok hogyan kerülhetik el a sötétben való tapogatózást.

A 3. fejezetben láttuk, hogy a nem informált keresési stratégiák oly módon képesek problémák megoldásait megtalálni, hogy szisztematikusan új állapotokat generálnak és összehasonlítják azokat a célállapottal. Sajnos ezek a stratégiák a legtöbb esetben hihetetlenül rossz hatékonysággal dolgoznak. Ezen fejezet megmutatja, hogy egy – problémaspecifikus tudást alkalmazó – informált keresési stratégia hatékonyabban képes a megoldást megtalálni. A 4.1. alfejezet bemutatja a 3. fejezetben tanulmányozott algoritmusok informált változatait, a 4.2. alfejezet pedig elmagyarázza, hogy a szükséges problémaspecifikus információ hogyan szerezhető meg. A 4.3. és a 4.4. alfejezet olyan algoritmusokkal foglalkozik, amelyek az állapottérben tisztán lokális keresést (local search) hajtanak végre, egy vagy több aktuális állapotot értékelve és módosítva ahelyett, hogy szisztematikusan tárnák fel az utat a kezdeti állapottól indulva. Ezek az algoritmusok olyan problémák esetén jók, ahol az útköltség közömbös, és az egyetlen, ami számít, hogy megtaláljuk-e a megoldást. A lokális keresési algoritmusok családjába a statisztikai fizika inspirálta módszerek (szimulált lehűtés, simulated annealing) és az evolúciós biológia sugallta módszerek (genetikus algoritmusok, genetic algorithms) is beletartoznak. A 4.5. alfejezet végül az online kereséssel (online search) foglalkozik, ahol az ágens egy teljesen ismeretlen állapottérrel találja magát szembe.