{"id":772,"date":"2018-06-29T23:30:27","date_gmt":"2018-06-30T03:30:27","guid":{"rendered":"http:\/\/aristotle2digital.blogwyrm.com\/?p=772"},"modified":"2018-06-28T23:52:40","modified_gmt":"2018-06-29T03:52:40","slug":"tweaks-and-kinks-in-the-a","status":"publish","type":"post","link":"https:\/\/aristotle2digital.blogwyrm.com\/?p=772","title":{"rendered":"Tweaks and Kinks in the A*"},"content":{"rendered":"

Two earlier posts (An A* Drama<\/a><\/em> and A Cross-Country A*<\/a><\/em>) introduced the A* algorithm, how it manages to find the shortest path (more on this below), and how it can also handle terrain costs.\u00a0 This post was meant to cover a minor point that was purposely omitted until now.<\/p>\n

Unfortunately, this post must also serve as a mea culpa<\/em> in which I need to apologize for a gross error in my previous two explanations.\u00a0 The error became apparent as I worked up this column for last month\u2019s installment and the discovery of the error derailed that post in favor of the one on compression and the pigeon hole principle<\/a>.<\/p>\n

In the previous two A* posts, the explanation stated that the scoring of the spots placed on the open list consisted of two parts: 1) the terrain cost (the cost to move onto the spot) and 2) the heuristic cost (an estimate of how far the spot is from the goal).\u00a0 I forgot to include the total cost from the starting space, which is the sum total of all the movement costs to get to that spot.\u00a0 Tracking that cost is vital to performing the re-parenting step that takes out any \u2018kinks\u2019 in the path that result from random choices the algorithm must make when picking between two spots of equal cost.<\/p>\n

Despite this omission, the algorithm actually performed quite well in the two cases examined and it found the shortest pay in the wayfarer example (A Cross-Country A*<\/a><\/em>) where the terrain costs were the primary driver and no obstacles were present.\u00a0 It fared slightly worse in the original example with the angry snake and the man who poked him (An A* Drama<\/a><\/em>), finding almost the shortest path, being only one step too long.\u00a0 Sadly, that error escaped my notice for some time.<\/p>\n

Fortunately, the error came and presented itself quite clearly when I returned to the snake v. man drama to explain re-parenting. \u00a0\u00a0To see what re-parenting involves consider this step in the snake\u2019s pursuit of his vengeance.<\/p>\n

\"\"<\/a><\/p>\n

Faced with two spaces, (7,1) and (7,2), with the same total cost of 8 \u2013 1 for terrain (upper right) and 4 for the heuristic (lower left), for a movement cost of 5 (lower right), and a cost of 3 steps from the starting space (black square in the center) \u2013 the snake randomly chooses to explore gird space (7,2).\u00a0 Doing so opens up (i.e. places on the open list) spots (7,1), (8,1), (6,2), (8,2), (6,3), (7,3), and (8,3), parents them all to (7,2), and scores them all as having a total cost from the starting space of 4, since any path to these spaces must first go through (7,2), which is 3 steps away from the starting space.<\/p>\n

The key point to note, is that the shortest path from the starting space to spaces (6,3) and (7,3) (for a total cost from start of 3) passes through spot (6,2), which is not explored first because of its greater cost.\u00a0 As a result, the current path to either (6,3) or (7,3) first goes past them to the right while it approaches from below before going back to the left as it arrives; the last three spots in the path are connected as (6,1) -> (7,2) -> (6,3).\u00a0 Because of its shape, I call such a sub-optimal path a kink.<\/p>\n

Now that we recognized the kink, what are we to do with it?\u00a0 Well, for the time being we just let it alone.\u00a0 When the algorithm finally explores one of these points, we simply look to see if shifting its parent from (7,2) to some other nearby space will lower the total cost from the starting spot.\u00a0 If so, then the parent is changed and the algorithm continues essentially unchanged.<\/p>\n

To be concrete, consider the situation a bit further in the snake\u2019s search for a path to his foe.\u00a0 After meandering in the lower right for a while, the snake\u2019s exploration has carried him to space (7,3), which, as a reminder, has received a total cost from the start space of 4 and which is parented to (7,2).<\/p>\n

\"\"<\/a><\/p>\n

As the snake explores space (7,3), he looks around to see if re-parenting the space to any of the neighboring spaces will lower the total cost from the starting space.\u00a0 He notes that re-parenting (7,3) to (6,2) will lower that total cost from the starting space by 1 and he does so.\u00a0 The box containing the new cost has been colored orange to reflect this change.<\/p>\n

\"\"<\/a><\/p>\n

Because (7,4) had been opened and scored when (8,3) was explored, it also will be re-parented when the snake recognizes the strategic importance of slithering through (7,4).<\/p>\n

The final path requires the snake to make 10 steps to reach his victim.<\/p>\n

\"\"<\/a><\/p>\n

It is a matter of a few minutes of playing with other paths to convince oneself that this is the smallest cost to wreak his revenge.\u00a0 Of course, the path passing through (6,3) -> (7,4) is equally short but won\u2019t be found by the A* since the heuristic scoring tends to pull the paths to the right even though the \u2018escape route\u2019 requires moving to the left.\u00a0 Also note, that without re-parenting, the kink would have cost an extra step, driving the total cost to 11.<\/p>\n

So, there you have it.\u00a0 A corrected and complete presentation of the A* algorithm.\u00a0 Sorry for the confusion, but, at least, the error helped to frame the importance of re-parenting in finding the shortest path.<\/p>\n","protected":false},"excerpt":{"rendered":"

Two earlier posts (An A* Drama and A Cross-Country A*) introduced the A* algorithm, how it manages to find the shortest path (more on this below), and how it can… Read more ><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-772","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/772","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=772"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/772\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=772"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=772"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=772"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}