Homework #3: IDA*
Submit Assignment
Due Apr 16 by 11:59pm Points 100 Submitting a file upload Available after Apr 9 at 12am
HW #2
Due April 16, 2018 at 11:59pm
For this assignment, undergraduates may work in teams with up to one other student, while graduate students must work individually. You can discuss the assignment with other students in thinking about how to solve these problems, but all programming and other portions of the assignment must be entirely your own work. You may not show your code to other students. If you are working with another student, you need to designate this by forming a group in Canvas.
This assignment should be turned in using Canvas.
Task:
In this assignment you will implement IDA* for the Sliding Tile Puzzle with Manhattan Distance for a heuristic.
Algorithm:
Implement the IDA* algorithm. The algorithm should take the environment, start and goal states, as well as a heuristic function. While the heuristic function can be part of the state, in the next assignment you will need to have heuristics that are not part of the state, so you may want to consider a separate heuristic function. (In C++ this could be implemented by a function pointer, a template parameter, or a pure virtual class.)
IDA* should return the path found.
Testing:
Test instances for IDA* will be provided shortly. Additionally, you should compare the speed of your IDA* implementation to DFID.
What to turn in:
Your submission should include the code for IDA* and a readme that contains the output of the test instances. Graduate students should also include a formal writeup that provides the experimental results in tables and explains the algorithms, domains, as well as the final results.
Test Instances:
Co rse Chat
Course Chat
There are 20 test instances in the transcript below. Your program should be able to solve all of them, but the last instance takes some time.
312 645 780 9 10 11 12 13 14
Starting IDA (MD):
Goal found at cost 4; 4 total expansions 0.00s elapsed
Left Left Up Up
341
602
785
9 10 11
12 13 14
Starting IDA (MD):
Goal found at cost 8; 8 total expansions 0.00s elapsed
Up Right Down Down Left Left Up Up 341
682
975
10 13 11
12 14 0
Starting IDA (MD):
Bound 12 complete; 7 total expansions (7 new)
Goal found at cost 14; 22 total expansions
0.00s elapsed
Left Up Left Up Right Up Up Right Down Down Left Left Up Up 031
648
972
10 13 5
12 14 11
Starting IDA (MD):
Bound 14 complete; 3 total expansions (3 new)
Bound 16 complete; 18 total expansions (15 new)
Bound 18 complete; 64 total expansions (46 new)
Goal found at cost 20; 169 total expansions
0.00s elapsed
Right Down Right Down Down Down Left Up Left Up Right Up Up Right Down Down Left Left Up Up 631
408
972
10 13 5
12 14 11
3 people online
New message alerts
Send
Co rse Chat
Course Chat
Starting IDA (MD): Bound 16 complete; 7 total expansions (7 new) Bound 18 complete; 44 total expansions (37 new)
Goal found at cost 20; 124 total expansions 3
New message
0.00s elapsed Right Down Down Down Left Up Left Up Right Up Left Up Right Right Down Down Left Left Up Up
630 981 742 10 13 5 12 14 11
people
online
alerts
Starting IDA (MD):
Bound 20 complete; 17 total expansions (17 new)
Bound 22 complete; 139 total expansions (122 new)
Goal found at cost 24; 408 total expansions
0.00s elapsed
Down Down Left Left Up Up Right Right Down Down Down Down Left Up Left Up Right Up Right Down Left Left Up Up
631
908
742
10 13 5
12 14 11
Starting IDA (MD):
Bound 18 complete; 9 total expansions (9 new)
Bound 20 complete; 61 total expansions (52 new)
Bound 22 complete; 313 total expansions (252 new)
Goal found at cost 24; 475 total expansions
0.00s elapsed
Right Down Left Left Up Up Right Right Down Down Down Down Left Up Left Up Right Up Right Down Left Lef t Up Up
061
938
742
10 13 5
12 14 11
Starting IDA (MD):
Bound 18 complete; 3 total expansions (3 new)
Bound 20 complete; 26 total expansions (23 new)
Bound 22 complete; 139 total expansions (113 new)
Bound 24 complete; 602 total expansions (463 new)
Goal found at cost 26; 1155 total expansions
0.00s elapsed
Right Down Right Down Left Left Up Up Right Right Down Down Down Down Left Up Left Up Right Up Right Do wn Left Left Up Up
610
938
742
10 13 5
12 14 11
Starting IDA (MD): Bound 16 complete; 1 total expansions (1 new)
Send
Co rse Chat
Course Chat
Bound 18 complete; 10 total expansions (9 new) Bound 20 complete; 52 total expansions (42 new) Bound 22 complete; 221 total expansions (169 new) Bound 24 complete; 859 total expansions (638 new) Goal found at cost 26; 1155 total expansions 0.00s elapsed
Left Down Right Down Left Left Up Up Right Right Down Down Down n Left Left Up Up
618
924
730 10 13 5 12 14 11
Starting IDA (MD):
Bound 18 complete; 6 total expansions (6 new)
Bound 20 complete; 43 total expansions (37 new)
Bound 22 complete; 235 total expansions (192 new)
Bound 24 complete; 982 total expansions (747 new)
Bound 26 complete; 3820 total expansions (2838 new)
Goal found at cost 28; 4402 total expansions
0.00s elapsed
Left Left Up Up Right Right Down Left Up Right Down Down Down Down Left Up Left Up Right Up Right Down Left Left Up Right Up Left
618
924
7 5 13
10 14 3
0 12 11
Starting IDA (MD):
Bound 24 complete; 19 total expansions (19 new)
Bound 26 complete; 132 total expansions (113 new)
Bound 28 complete; 753 total expansions (621 new)
Bound 30 complete; 3615 total expansions (2862 new)
Bound 32 complete; 16221 total expansions (12606 new)
Goal found at cost 34; 56122 total expansions
0.03s elapsed
Right Up Up Right Down Left Up Left Up Up Right Right Down Left Up Right Down Down Down Down Left Up Le ft Up Right Up Right Down Left Left Up Right Up Left
618
902
754
14 12 13
10 11 3
Starting IDA (MD): Bound 28 complete; 6 total expansions (6 new) Bound 30 complete; 151 total expansions (145 new) Bound 32 complete; 1153 total expansions (1002 new) Bound 34 complete; 6596 total expansions (5443 new) Bound 36 complete; 34600 total expansions (28004 new) Bound 38 complete; 172472 total expansions (137872 new) Bound 40 complete; 816577 total expansions (644105 new) Goal found at cost 42; 1872632 total expansions 0.79s elapsed
3 people online
New
message
alerts
Down Left Up Left Up Right Up Right Dow
Send
Co rse Chat
Course Chat
Right Down Down Down Left Up Left Up Up Up Right Down Right Up Left Down Down Down Right Up Left Down L eft Down Right Right Up Up Up Left Down Down Down Right Up Left Left Up Up Right Up Left
618
952
7 12 4 14 13 3 10 11 0
Starting IDA (MD):
Bound 26 complete; 16 total expansions (16 new)
Bound 28 complete; 136 total expansions (120 new)
Bound 30 complete; 724 total expansions (588 new)
Bound 32 complete; 3383 total expansions (2659 new)
Bound 34 complete; 15302 total expansions (11919 new)
Bound 36 complete; 68338 total expansions (53036 new)
Bound 38 complete; 301299 total expansions (232961 new)
Goal found at cost 40; 324646 total expansions
0.14s elapsed
Left Left Up Right Right Down Left Left Up Up Right Down Left Up Up Up Right Down Right Up Left Down Do wn Right Down Down Left Left Up Up Up Right Down Down Right Up Up Up Left Left
618
952
7 12 4
14 0 13
10 11 3
Starting IDA (MD):
Bound 28 complete; 67 total expansions (67 new)
Bound 30 complete; 489 total expansions (422 new)
Bound 32 complete; 2545 total expansions (2056 new)
Bound 34 complete; 11907 total expansions (9362 new)
Bound 36 complete; 55355 total expansions (43448 new)
Bound 38 complete; 253221 total expansions (197866 new)
Bound 40 complete; 1129711 total expansions (876490 new)
Goal found at cost 42; 1941611 total expansions
0.84s elapsed
Right Down Left Left Up Right Right Down Left Left Up Up Right Down Left Up Up Up Right Down Right Up L eft Down Down Right Down Down Left Left Up Up Up Right Down Down Right Up Up Up Left Left
618
952
7 12 4
14 0 11
10 3 13
Starting IDA (MD): Bound 24 complete; 37 total expansions (37 new) Bound 26 complete; 195 total expansions (158 new) Bound 28 complete; 835 total expansions (640 new) Bound 30 complete; 3461 total expansions (2626 new) Bound 32 complete; 14361 total expansions (10900 new) Bound 34 complete; 58964 total expansions (44603 new) Bound 36 complete; 238556 total expansions (179592 new) Goal found at cost 38; 254137 total expansions 0.12s elapsed Left Up Right Right Down Left Left Up Up Up Right Down Right Up Left Down Down Down Down Left Up Up Rig ht Down Down Right Up Up Up Left Down Left Up Right Right Up Left Left
3 people online
New message alerts
Send
Co rse Chat
Course Chat
618 952 7 12 4 14 0 11 10 3 13
Starting IDA (MD):
Bound 24 complete; 37 total expansions (37 new)
Bound 26 complete; 195 total expansions (158 new)
Bound 28 complete; 835 total expansions (640 new)
Bound 30 complete; 3461 total expansions (2626 new)
Bound 32 complete; 14361 total expansions (10900 new)
Bound 34 complete; 58964 total expansions (44603 new)
Bound 36 complete; 238556 total expansions (179592 new)
Goal found at cost 38; 254137 total expansions
0.11s elapsed
Left Up Right Right Down Left Left Up Up Up Right Down Right Up Left Down Down Down Down Left Up Up Rig ht Down Down Right Up Up Up Left Down Left Up Right Right Up Left Left
618
952
7 12 4
10 14 11
3 13 0
Starting IDA (MD):
Bound 20 complete; 1 total expansions (1 new)
Bound 22 complete; 20 total expansions (19 new)
Bound 24 complete; 85 total expansions (65 new)
Bound 26 complete; 332 total expansions (247 new)
Bound 28 complete; 1256 total expansions (924 new)
Bound 30 complete; 4598 total expansions (3342 new)
Bound 32 complete; 17165 total expansions (12567 new)
Bound 34 complete; 64458 total expansions (47293 new)
Bound 36 complete; 242464 total expansions (178006 new)
Bound 38 complete; 920272 total expansions (677808 new)
Goal found at cost 40; 1066547 total expansions
0.49s elapsed
Left Left Up Up Right Right Down Left Left Up Up Up Right Down Right Up Left Down Down Down Down Left U p Up Right Down Down Right Up Up Up Left Down Left Up Right Right Up Left Left
618
952
7 12 4
10 0 14
3 13 11
Starting IDA (MD): Bound 20 complete; 8 total expansions (8 new) Bound 22 complete; 40 total expansions (32 new) Bound 24 complete; 168 total expansions (128 new) Bound 26 complete; 626 total expansions (458 new) Bound 28 complete; 2270 total expansions (1644 new) Bound 30 complete; 8339 total expansions (6069 new) Bound 32 complete; 30778 total expansions (22439 new) Bound 34 complete; 113944 total expansions (83166 new) Bound 36 complete; 427498 total expansions (313554 new) Bound 38 complete; 1612386 total expansions (1184888 new)
3 people online
New message alerts
Send
Co rse Chat
Course Chat
Goal found at cost 40; 1941238 total expansions 0.83s elapsed Left Up Right Down Left Down Right Right Up Left Left Up Right Down Down Left Up Up Up Up Right Down Ri
ght Up Left Down Down Right Down Left Left Up Up Right Down Right Up Up Left L3eft
New message alerts
6 1 8 9 5 2 10 7 4 12 0 14 3 13 11
people online
Starting IDA (MD):
Bound 18 complete; 1 total expansions (1 new)
Bound 20 complete; 15 total expansions (14 new)
Bound 22 complete; 60 total expansions (45 new)
Bound 24 complete; 225 total expansions (165 new)
Bound 26 complete; 799 total expansions (574 new)
Bound 28 complete; 2863 total expansions (2064 new)
Bound 30 complete; 10089 total expansions (7226 new)
Bound 32 complete; 36650 total expansions (26561 new)
Bound 34 complete; 133936 total expansions (97286 new)
Bound 36 complete; 496216 total expansions (362280 new)
Goal found at cost 38; 962251 total expansions
0.41s elapsed
Right Up Left Left Down Down Right Up Left Up Right Down Right Down Left Left Up Up Up Up Right D ght Up Left Down Down Down Left Up Up Right Down Right Up Up Left Left
5 13 14
2 4 12
068
319
11 7 10
Starting IDA (MD): Bound 34 complete; 10 total expansions (10 new) Bound 36 complete; 50 total expansions (40 new) Bound 38 complete; 213 total expansions (163 new) Bound 40 complete; 1041 total expansions (828 new) Bound 42 complete; 4833 total expansions (3792 new) Bound 44 complete; 24432 total expansions (19599 new) Bound 46 complete; 130285 total expansions (105853 new) Bound 48 complete; 711122 total expansions (580837 new) Bound 50 complete; 3882754 total expansions (3171632 new) Bound 52 complete; 21006744 total expansions (17123990 new) Bound 54 complete; 112060368 total expansions (91053624 new) Goal found at cost 56; 269285567 total expansions 113.62s elapsed Right Down Left Up Right Up Up Left Down Down Right Right Up Left Down Down Down Right Up Up Up Up Left Left Down Down Right Down Right Up Up Left Left Down Down Right Down Right Up Up Left Down Down Left Up Right Down Right Up Left Up Right Up Up Left Left Program ended with exit code: 0
own Ri
Send
Homework 3: IDA*
Co rse Chat
Course Chat
Criteria
Ratings
Pts
IDA* Implementation
The algorithm should take the environment, start and goal states, as well as a heuristic function.
60.0 pts Undergraduate Full Marks
50.0 pts
3
Graduate
0.0 pts
New
No
people
Full
online
Marks
message 60.0 pts Marks
alerts
Testing
Tests should be run against the provided test instances for IDA*. Additionally, you should compare the speed of your IDA* implementation to DFID. Provide a readme that contains the output of the test instances.
25.0 pts Undergraduate Full Marks
20.0 pts Graduate Full Marks
0.0 pts No Marks
25.0 pts
Manhattan Distance Heuristic Function
While the heuristic function can be part of the state, in the next assignment you will need to have heuristics that are not part of the state, so you may want to consider a separate heuristic function.
15.0 pts Undergraduate Full Marks
10.0 pts Graduate Full Marks
0.0 pts No Marks
15.0 pts
GRAD ONLY Write up
20.0 pts Full Marks
0.0 pts
No Marks
Total Points: 120.0
2
0.0 pts
Send
Co rse Chat