Vacuum Cleaner World Problem

Nina Rubanovich, Jade Neeley 🙂, Gavin Boley

Our group used Python on a Github Repository and ran our program on our laptops. The repository can be found at: https://github.com/NinaRubanovich/Homework2/tree/master .

Problem Instance 1

Initial Location: (2, 2)

Dirty Squares: [(1, 2), (2, 4), (3, 5)]

Uniform Cost Tree Search

Path: ('Up', 'Down', 'Right', 'Right', 'Down', 'Right')

Nodes Expanded: 1321

Nodes Generated: 4471

Execution Time (s): 0.2973511219024658

Number of Moves in Solution: 6

Cost of Solution: 4.9

Uniform Cost Graph Search

Path: ('Up', 'Down', 'Right', 'Right', 'Down', 'Right')

Nodes Expanded: 1304

Nodes Generated: 4441

Execution Time (s): 0.2837197780609131

Number of Moves in Solution: 6

Cost of Solution: 4.9

Iterative Deepening Tree Search

Path: ('Up', 'Down', 'Right', 'Right', 'Down', 'Right')

Nodes Expanded: 756

Nodes Generated: 2541

Execution Time (s): 0.19977903366088867

Number of Moves in Solution: 6

Cost of Solution: 4.9

Problem Instance 2

Initial Location: (3, 2)

Dirty Squares: [(1, 2), (2, 1), (2, 4), (3, 3)]

Uniform Cost Tree Search

Path: ('Right', 'Right', 'Up', 'Left', 'Left', 'Up', 'Down', 'Left')

Nodes Expanded: 26434

Nodes Generated: 88099

Execution Time (s): 170.33823204040527

Number of Moves in Solution: 8

Cost of Solution: 7.1

Uniform Cost Graph Search

Path: ('Right', 'Up', 'Right', 'Left', 'Left', 'Up', 'Down', 'Left')

Nodes Expanded: 26027

Nodes Generated: 86607

Execution Time (s): 448.6521439552307

Number of Moves in Solution: 8

Cost of Solution: 7.1

Iterative Deepening Tree Search

Path: ('Right', 'Right', 'Up', 'Left', 'Left', 'Up', 'Down', 'Left')

Nodes Expanded: 8509

Nodes Generated: 28533

Execution Time (s): 47.01594805717468

Number of Moves in Solution: 8

Cost of Solution: 7.1