Artificial Intelligence Strategies, Applications, and Models Through SEARCH

Page iii

Artificial Intelligence

Strategies, Applications, and Models Through Search Second Edition

CHRISTOPHER THORNTON

BENEDICT du BOULAY

AMACOM

New York · Atlanta · Boston · Chicago · Kansas City · San Francisco · Washington, D.C.

Brussels · Mexico City · Tokyo · Toronto

Page iv

© 1998 Intellect

ISBN: 0-8144-0470-7

All rights reserved. No part of this book may be reproduced in any form or by any means, electronic,

mechanical photocopying, recording, or otherwise without the prior written permission of the publisher.

Printed in the United States of America.

AMACOM

AMERICAN MANAGEMENT ASSOCIATION

1601 Broadway

New York, New York 10019

Visit the American Management Association and

AMACOM on-line at:

http://www.amanet.org

Page v

Foreword

This book started out as a set of notes for a POP-11 based course at the University of Sussex on an

introduction to Artificial Intelligence. Chris Thornton designed this course around the fundamental idea

of search and devised the basic structure of the book. The course expanded to take in Prolog and was

then taught by Benedict du Boulay. He added Prolog variants to the POP-11 code. The course is now

taught by Steve Easterbrook who made several helpful comments on a draft of the book, as did Mike

Sharples. We thank Aaron Sloman and David Hogg for use of their method of writing a simple natural

language interface to a blocksworld, and Allan Ramsay and Rosalind Barrett for permission to adapt

their "weather rules" in the chapter on expert systems. We also thank various Sussex students who

pointed out errors and omissions, particularly Sarah Cole, who carefully proof-read parts of an earlier

draft. The programs were developed and the book written using the POPLOG programming

environment.

Benedict du Boulay would like to dedicate his contribution to this book to his friend Hugh Noble with

whom he started to write a text book not unlike this one but never finished it.

Page vii

Contents

1 Search-Related Techniques in AI 1

Why search 1

Objectives 2

Problem solving systems 3

State space search and problem reduction 4

Blind search and heuristic search 5

Graphs and trees 7

Organisation of the book 8

Searching for a solution path in a state space 8

Problem reduction 10

A very brief comparison of POP-11 and Prolog 13

Further reading 14

2 Simple State Space Search 15

Path-finding 15

Setting up the database 16

Setting up the path-finding function 19

The generality of search 24

Search spaces and search trees 24

Constructing an explicit representation of the search-tree 27

Search graphs 29

Node terminology 32

Backwards v. forwards searching 32

OR-tree search in Prolog 33

Reading 40

Exercises 40

Page viii

3 State Space Search 43

Introduction 43

The water jugs problem 43

Constructing successor nodes 44

The problem space 48

Searching for a solution path 50

Problem space exploration strategies 52

Breadth-first search 53

Agendas 54

Implementing depth-first search using an agenda 58

Iterative deepening 59

Water jugs in Prolog 60

Agendas in Prolog 62

Iterative deepening in Prolog 67

Reading 68

Exercises 68

Notes 69

4 Heuristic State Space Search 71

Introduction 71

The 8-puzzle 71

Constructing 8-puzzle successors 72

Heuristic search 77

Hill-climbing search 81

Heuristic breadth-first search 83

Ordered search and the A* Algorithm 86

Heuristic Search in Prolog 92

Reading 103

Exercises 103

Notes 105

5 Heuristic Search of Game Trees 107

Computing successors in the game of nim 109

Minimax evaluation 110

Worked example 116

Alpha-beta cutoffs 117

Implementing a nim-playing program 121

Page ix

Minimaxing in Prolog 125

Reading 130

Exercises 131

Notes 131

6 Problem Reduction (AND/OR-tree search) 133

Introduction 133

Problem-reduction and the Tower of Hanoi 133

Implementing arbitrary AND/OR-trees 136

Implementing the AND/OR-tree search function 138

Implementing planning as AND/OR-tree search 139

Implementing reasoning as AND/OR-tree search 141

Loops in the search space 145

Solution tree 150

The AND/OR search tree 153

State space search and problem reduction 155

Forward AND/OR-tree search 159

Terminology 161

Production systems 162

AND/OR Search in Prolog 162

Reading 168

Exercises 168

Notes 169

7 Planning (microworld search) 171

Introduction 171

Operators 173

Strategies for microworld search 174

Implementing the new search function 177

Difference tables 183

Goal interactions 183

Operators containing variables 187

Simple plan finding in Prolog 194

Reading 199

Exercises 199

Page x

8 Parsing (search as analysis) 201

Introduction 201

Solution trees as analyses 201

Parsing 204

Data-driven (bottom-up) parsing 210

Building trees bottom-up 212

Advantages of bottom-up search 216

Backwards and forwards parsing in Prolog 216

The Prolog grammar rule formalism 219

Bottom-up parsing in Prolog 221

Why is parsing useful 225

Building a top-level interpreter 231

Meaning in Prolog 234

Reading 240

Exercises 240

9 Expert Systems (probabilistic search) 243

Introduction 243

Probabilistic rules 244

Basic probability theory 245

Fuzzy set theory 246

MYCIN-like search 247

Implementing certainty-factors 251

Forwards or backwards 256

Probabilistic search in Prolog 258

Reading 265

Exercises 265

10 Concept learning (description search) 267

Introduction 267

Generalisation hierarchies 269

Deriving extensions 271

Quantifying generality 275

Concept learning 278

Implementing the generalisation mechanism 278

The focussing algorithm 282

Focussing in Prolog 283

Page xi

Generalisation as search 288

Reading 290

Exercises 290

11 Prolog (search as computation) 293

Introduction 293

Search rules as predicates 293

The use of variables in search rules 295

Data structures 297

Unification 299

Implementing the unification matcher 301

Machinery to deliver output 306

The search function 306

Programming in Toyplog 310

A sample interaction with Toyplog 315

Reading 318

Exercises 318

Notes 319

References 321

Appendix A: Introduction to POP-11 325

Starting POP-11 325

POP -11 as a calculator 325

Variables 327

Functions 328

Defining functions 329

Local variables 331

Boolean expressions 333

Conditionals 335

Words and lists 337

Hats 339

For loops 340

Applist 342

Syssort 343

Matching 344

Restriction procedures 345

The matcher arrow 348

Page xii

The database 349

Readline 351

Functions calling functions 352

Recursion 353

Tracing 354

Show tree 356

Exiting from a function 357

Partial application 358

Concluding comment 358

Index 359

Page xiii

Table of Figures

1-1. State-space search building the solution, a path 6

1-2. State-space search building the search tree, an OR tree 9

1-3. Problem reduction search 11

1-4. Problem reduction search building the solution, an AND tree 12

1-5. Comparison of POP-11 and Prolog 13

2-1. Map of Brighton 16

2-2. Computing successors 18

2-3. A true/false search function 20

2-4. Searching for a solution path 22

2-5. A search tree 26

2-6. A map of toytown 27

2-7. Computing the search tree 28

2-8. The search tree for Z from A 29

2-9. The search graph for Z from A 30

2-10. Searching with no location visited more than once 31

2 -1 1 .A tree 33