Name :- Ishan Adhaulia

Enroll no. :- IIT2011133

Subject :- RMP
Assignment -2

Answer 1 :-
1. Human Computer Interaction a. Global Positioning System(4)
2. Data Acquisition b. Trajectory Generation(8)
3. Computer Vision c. Motion Tracking(5)
4. Global Level Localization d. GoogleMaps(6)
5. Local Level Localization e. Reference speeds/accelerations(2)
6. Global Mapping f. Grid world(7)
7. Local Mapping g. Trajectory Correction(9)
8. Planning h. Read Sensor Values(10)
9. Re-planning i. Obstacle type, shape and size(3)
10. Control j. Task specification(1)





Answer 2:-






Answer 3:-
BUG 0



BUG 1 Solutions






Answer 4:-
Bug 1
Let qL0= qstart;
i = 1
repeat
repeat
from qLi-1 move toward qgoal
until goal is reached or obstacle encountered at qHi
if goal is reached, exit
repeat
//this is the required change in the
follow boundary recording pt qLi for pivot with shortest distance to goal and rotate the links
accordingly to move along the boundary.
until qgoal is reached or qHi is re-encountered
if goal is reached, exit
Go to qLi
if move toward qgoal moves into obstacle
exit with failure
else
i=i+1
continue








Bug 2
Let qL0= qstart; i = 1
repeat
repeat
from qLi-1 move toward qgoal along the m-line
until goal is reached or obstacle encountered at qHi
if goal is reached, exit
repeat
//this is the required change in the pseudocode
adjust(rotation) of the 2link as one link can follow boundary
until qgoal is reached or qHi is re-encountered or m-line is re-encountered,
x is not qHi , d(x,qgoal) < d(qHi,qgoal) and way to goal is unimpeded
if goal is reached, exit
if qHi is reached, return failure
else
qLi = m
i=i+1
continue



Answer 5
On increasing the sensing range in tangent bug, the effect to the optimality and completeness is that
the algorithm performs much better than before in real time. As information of far and big obstacles
can be processed early and definitive re-planning can be done easily.
Further denote which of Bug0, Bug1 and Bug2 algorithms are best suited for
(i) A map filled with only circular non-overlapping and sparse obstacles => Bug0
(ii) A map filled with regular polygon shaped, convex, non-overlapping obstacles=> Bug2
(iii) A map which can have concave obstacles => Bug1
Answer 6
Assuming the weight of edge between E and H is 1.
By Uniform Cost Search
Diagram 1
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {B,C}, close = {A}, cost = 0 , path ={A}
Step 3 : open = {C,D}, close = {A,B}, cost = 2 , path ={A,B}
Step 4 : open = {D}, close = {A,B,C}, cost = 2, path ={A,B}
Step 5 : open = {E}, close = {A,B,C,D}, cost =7 , path ={A,B,D}
Step 6 : open = {G, F, H}, close = {A,B,C,D,E}, cost =9 , path ={A,B,D,E}
Step 7 : open = {F, H}, close = {A,B,C,D,E,G}, cost =12 , path ={A,B,D,E,G}
Step 8 : open = {F}, close = {A,B,C,D,E,G, H}, cost =12 , path ={A,B,D,E,G}
Step 9 : open = {}, close = {A,B,C,D,E,G, H}, cost =12 , path ={A,B,D,E,G}
UCS first visits the node with the shortest path costs(sum of edge weights) from the root node.
Diagram 2
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {D,B}, close = {A}, cost = 0 , path ={A}
Step 3 : open = {B,C}, close = {A,D}, cost = 2 , path ={A,D}
Step 4 : open = {C}, close = {A,D,B}, cost = 2, path ={A,D}
Step 5 : open = {G}, close = {A,D,B,C}, cost =3 , path ={A,D,C}
Step 6 : open = {}, close = {A,D,B,C,G}, cost =8 , path ={A,D,C,G}




By BFS
Diagram 1
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {B,C}, close = {A}, cost = 0 , path ={A}
Step 3 : open = {C,D}, close = {A,B}, cost = 2 , path ={A,B}
Step 4 : open = {D}, close = {A,B,C}, cost = 2, path ={A,B}
Step 5 : open = {E}, close = {A,B,C,D}, cost =7 , path ={A,B,D}
Step 6 : open = {G, F, H}, close = {A,B,C,D,E}, cost =9 , path ={A,B,D,E}
Step 7 : open = {G, F }, close = {A,B,C,D,E,H}, cost =10 , path ={A,B,D,E,H}
Step 8 : open = { F }, close = {A,B,C,D,E,H, G}, cost =11 , path ={A,B,D,E,H, G}
Step 9 : open = { }, close = {A,B,C,D,E,H, G, F}, cost =11 , path ={A,B,D,E,H, G}
BFS first visits the node with the shortest path length (number of nodes) from the root node.
Diagram 2
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {D,B}, close = {A}, cost = 0 , path ={A}
Step 3 : open = {B,C}, close = {A,D}, cost = 2 , path ={A,D}
Step 4 : open = {C}, close = {A,D,B}, cost = 2, path ={A,D}
Step 5 : open = {G}, close = {A,D,B,C}, cost =3 , path ={A,D,C}
Step 6 : open = {}, close = {A,D,B,C,G}, cost =8 , path ={A,D,C,G}






By Heuristic Search

Diagram 1
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {C,B}, close = {A}, cost = 0, path ={A}
Step 3 : open = {D,B}, close = {A,C}, cost = 3, path ={A,C}
Step 4 : open = {E,B}, close = {A,C,D}, cost = 8, path ={A,C,D}
Step 5 : open = {G,H,F,B}, close = {A,C,D,E}, cost = 10, path ={A,C,D,E}
Step6 : open = {H,F,B}, close = {A,C,D,E,G}, cost = 13, path ={A,C,D,E,G}
Step7 : open = {F,B}, close = {A,C,D,E,G,H}, cost = 13, path ={A,C,D,E,G}
Step8 : open = {B}, close = {A,C,D,E,G,H,F}, cost = 13, path ={A,C,D,E,G}
Step9 : open = {}, close = {A,C,D,E,G,H,F,B}, cost = 13, path ={A,C,D,E,G}
Diagram 2
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {B,D}, close = {A}, cost = 0, path ={A}
Step 3 : open = {C,D}, close = {A,B}, cost = 4, path ={A,B}
Step 4 : open = {G,D}, close = {A,B,C}, cost = 6, path ={A,B,C}
Step 5 : open = {D}, close = {A,B,C,G}, cost = 11, path ={ A,B,C,G}
Step 6 : open = {}, close = {A,B,C,G,D}, cost = 11, path ={ A,B,C,G}
By A*
Diagram 1
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {B,C}, close = {A}, cost = 0, path ={A}
Step 3 : open = {C,D}, close = {A,B}, cost = 2, path ={A,B}
Step 4 : open = {D}, close = {A,B,C}, cost = 2, path ={A,B}
Step 5 : open = {E}, close = {A,B,C,D}, cost = 7 , path ={A,B,D}
Step 6: open = {H,G,F}, close = {A,B,C,D,E}, cost = 9, path ={A,B,D,E}
Step 7 : open = {G,F}, close = {A,B,C,D,E,H}, cost = 10, path ={A,B,D,E,H}
Step 8 : open = {F}, close = {A,B,C,D,E,H,G}, cost = 11, path ={A,B,D,E,H,G}
Step 9 : open = {}, close = {A,B,C,D,E,H,G,F}, cost = 11, path ={A,B,D,E,H,G}
Diagram 2
A- starting node G is goal
Step 1 : open = {A}, close = {}, cost = 0, path ={}
Step 2 : open = {B,D}, close = {A}, cost = 0, path ={A}
Step 3 : open = {D,C}, close = {A,B}, cost = 4, path ={A,B}
Step 4 : open = {C}, close = {A,B,D}, cost = 2, path ={A, D}
Step 5 : open = {G}, close = {A,B,C,D}, cost = 3, path ={A,D,C}
Step 6 : open = {}, close = {A,B,C,D, G}, cost = 8, path ={A,D,C,G}
For Diagram 1, our heuristic is admissible while for Diagram 2 it is consistent.
Used equations is h(x) <= d(x,y)+h(y) true for all set of points if it is , then it is admissible otherwise
consistent.

Final conclusion -: A* algorithm is most optimum.




Answer 7(i).
The effect of increasing resolution to the path length and execution time of the algorithm is that the
algorithm will return more optimum path but time required by the algorithm increases as well since the
search space is increased.
Answer 7(ii).
Yes , the homotopy returned by the A* algorithm changes on an increase in resolution as of now the
there are more levels of coloured cells are made, some are mixture of colours since it depends on the
%age of obstacle it had for the colour the cell obtained. So if there are the changes done on the states
only.
Answer 7(iii).
If the resolution increased is done only at the edges and corners for the given workspace, the optimality
of algorithm increases as it has better search tree and resolution is increased for part of workspace so
the search tree is too not so big. While for time computation is also increased but that is the tradeoff
we can afford for better planning results.
Answer 8.
Function A*(start, goal ) {
CLOSE = {};
Visited = empty vector;
OPEN = {start};
gscore[start] = 0;
fscore[start] = gscore[start]+h(start, goal);
while (!OPEN ) {
current = node having lowest fscore;
if (current = goal)
return path(visited, goal);
}
remove current from OPEN;
add current to CLOSE;
for each neighbor of current,
push them in OPEN if not present;
tentativegscore = gscore[current]+d(current, neighbor);
if (neighbor not in OPEN or tentativegscore < gscore[neighbor]) {
visited[neighbor] = current;
gscore[neighbor]= tentativegscore;
fscore[neighbor] = gscore[neighbor]+h(neighbor, goal);
}
}
For (i) part = >
Either q(A) or q(B)
Call Function A*(start, A) or Function A*(start, B );
For (ii) part =>
Call Function A*(start, A) and Function A*(start, B );
For (iii) part =>
Call Function A*(start, A) ;
Call Function A*(A, B );


Answer 9.
These are the following conditions when D* algorithm cannot handle the cases easily :-
=> A very large obstacle suddenly appearing in the map.
=> A complete change of the map.
=> The cost function is changed dynamically.
The reasons behind these problems are as the planning for the sudden appearing large obstacle takes
time as if we are using high resolution for optimization. Then sudden change results in the cost functions
which are not easier to incorporate in the re-planning for the robot.
If complete change of map is done, then we have to recalculate all the values for algorithm to run again
without any problem.
Explained above along with 1
st
problem.



Answer 10.
Case 1
Yes, both the algorithms would result in fairly similar performance. Since both the algos have
preprocessed the map and taken the decisions.
Heuristic algorithms are generally better than BUG 0 because they have a bound for the calculation of
path and time of completion depending upon the decision making of the robot.
Case 2
Generally A* algorithm outperforms the BUG1 algorithm as it takes less number of expansion steps and
somewhat give similar solution so the A* algorithm is preferred over BUG 1.
BUG 1 takes more time as it circumnavigate the whole obstacle before going toward goal if it faces an
obstacle.