Lecture 18: Uninformed and Heuristic Search

This lecture is part of the course “Foundations of Artificial Intelligence” developed by Dr. Ryan Urbanowicz in 2020 at the University of Pennsylvania’s Perelman School of Medicine. This is the first of three courses covering topics in artificial intelligence for application within the context of informatics and biomedical research. The course is divided into modules that cover (1) introductory/background materials, (2) logic, (3) other knowledge representation, (4) essentials of expert systems, (5) search, (6) uncertainty, and (7) advanced/auxiliary topics. These topics offer a global foundation for branches of AI application and research, including concepts that will later support a deeper understanding of inductive reasoning and machine learning. In a practical sense, this course focuses on how biomedical data can be organized, represented, interpreted, searched, and applied in order to derive knowledge, make decisions, and ultimately make predictions while avoiding bias. This course was assembled using content from a wide variety of textbooks, slides, and lectures by various authors and speakers on the relevant topics. Some lectures were prepared and given by guest lecturers and thus have not been posted. At the time of posting, this course is in its second year so any feedback is welcome regarding any mistakes or suggested improvements. Weblinks: http://ryanurbanowicz.com/ https://www.med.upenn.edu/urbslab/ https://github.com/UrbsLab Chapters: 0:00 Introduction 3:20 Breadth-First Search (Uninformed) 11:20 Depth-First Search (Uninformed) 19:54 Iterative Deepening Search (Uninformed) 23:44 Bidirectional Search (Uninformed) 25:19 Uniform Cost Search (Uninformed) 32:32 Introduction to Heuristic Search 36:59 Greedy Best-First Search (Heuristic) 42:43 The A* Algorithm (Heuristic) 46:43 Conclusion