Write an algorithm for a robot that has to get from point A to point B in a room.

I have a few clarifying questions before I start working on the problem - 

1. Can the robot travel diagonally if say point A and B are placed on the diagonal vertex of a rectangle? - No it can’t 

2. Is the plane 2D or 3D? - Consider it 2D for simplicity 

3. Does the Robot have to use the shortest path between A and B? - No it can travel any path it takes less time to reach the destination

4. Do we take into account curved paths or just straight paths? - Just the straight paths

5. Are there any obstacles in between or a clear path? - Yes, there are obstacles

6. In that case, are the Obstacles in each route known already or will they be known once the Robot reaches those obstacles? - Already known

7. Can I take a constant time required for the robot to overcome an obstacle, say 2 seconds? - Yes, that works 

8. Can I assume that the Robots move in values of 1 - for example robot is at coordinate 2 on x-axis, the next time it moves to the right it reaches 3 on x-axis for simplicity? - Yes you can assume that 

Thank you! Now I’ll start formulating an algorithm for the robot to reach its destination in the shortest time. 

So there are 4 steps that I figured out will be required to move the robot from point A to B. These steps in-turn form the 4 functions that we need to implement in order to form the algorithm. These steps are - 

1. Finding the Perpendiculars of point A and Point B which means the coordinates at which a perpendicular from point A and B intersects with coordinates axes.  

2. Find all the paths between point A and point B - Finding the coordinates between point A and point B on which the Robot can travel in a straight line. This can be found by the logic that  if the x coordinate of Robot is less than the x coordinate of the perpendicular dropping from B then the robot moves in the Right direction. Similarly if the y coordinate of Robot is less than the y coordinate of the perpendicular dropping from B then the robot moves in the Up direction. All these paths can be found by permutations of these conditions. 

3. Once all the paths have been found, we’ll know the number of obstacles in each path and this can be calculated by the time taken to overcome each obstacle (in this case we have assumed 2 seconds). This gives the minimum time it takes to travel from point A to point B, and the path taken to take this minimum time. 

4. Once we know the path (it looks something like an array of tuples that contain the coordinates that the robot needs to reach after each move to finally reach its Destination i.e. Point B - [(0, 0),(0, 1),(1, 1)… ]) a similar logic as that of point 2 can be used to move the Robot i.e. for each element of Path array if the first element i.e the x coordinate is greater than the x coordinate of robot’s current position then robot’s current position == x coordinate of the array element. Similarly if the y coordinate is greater than the y coordinate of robot’s current position then robot’s current position == y coordinate of the array element.  

The pseudo code for the above algorithm will look something like -

function moveBetweenPoints(pointA, pointB){

/* this array contains the tuples which have the coordinates of the path that takes shortest time. */

let shortestTimePath = [(), (), (), ()... ]

/* a function to move the robot from pointA to pointB via the path which takes the shortest time. */ 

moveRobot(pointA, pointB, shortestTimePath)

}

// a function to find the path which takes the shortest time in moving from pointA to pointB

function shortestTimePath(pointA, pointB){

let minTimeIndex = 0

/* this array contains arrays which has the tuples which have the coordinates of the paths that can be taken by the robot */

let paths = [[(), (), (), ()...]... ]

paths = findAllPaths(pointA, pointB)

/* this array contains the number of obstacles present in the position for the corresponding path in the paths array */

obstacles_num = [] 

/* if we encounter any obstacle in the paths we will add the number in the obstacles_num array in the corresponding index */  

for i in paths[]{

if Obstacle != NULL 

obstacles_num[i]++

else pass

} 

for i in obstacles_num[]{

if i == min(obstacles_num)

minTimeIndex = i 

} 

// returning the path that takes the minimum amount of time  

return path[minTimeIndex]

}

// a function to find all the paths between pointA and pointB

function findAllPaths(pointA, pointB){

/* this array contains arrays which has the tuples which have the coordinates of the paths that can be taken by the robot */

let paths = [[(), (), (), ()...]... ]

/* perpend_x, and perpend_y are the tuples that

contains the coordinates where the perpendicular from

pointA and pointB intersect with coordinate axes */  

let perpend_x, perpend_y = ()  

// this is a tuple that contains the position of the robot 

let robotPosition = ()

perpend_x = perpendicular_x(pointA, pointB)

perpend_y = perpendicular_y(pointA, pointB)

/* if the position of the x coordinate is greater than that

of current x coordinate of the robot

for i in all the permutations {

if perpend_x.1 > robotPosition.1 

robotPosition.1++

if perpend_x.2 > robotPosition.2 

robotPosition.2++ 

paths.append

}

return paths 

}

// a function to move the robot from pointA to pointB via the path that takes the shortest path

function moveRobot(pointA, pointB, shortestTimePath){

// this is a tuple that contains the position of the robot 

let robotPosition = ()

let secondLastPoint = ()

for i in shortestTimePath{

if robotPosition.1 != i.1

robotPosition.1 = i.1

if robotPosition.2 != i.2

robotPosition.2 = i.2

}

secondLastPoint = shortestTimePath(len(shortestTimePath)-1)

if robot.1 == secondLastPoint.1

 robot.1 = pointB.1

if robot.2 == secondLastPoint.2

 robot.2 = pointB.2

}