1

enter image description here

I am dealing with the following problem and i was looking to write a Pseudo-code for developing an algorithm that can be generic for such a problem.

Here is what i have come up with thus far.

STEP 1

In this step i try to get the robot where it maybe placed to the top left corner.

Turn Left -> If no window or Wall detected keep going forward 1 unit..

if window or wall detected ->Turn right --> if no window or Wall detected keep going forward..

if window or wall detected then top left corner is reached.

STEP 2 (We start counting windows after we get to this stage to avoid miscounting)

I would like to declare a variable called turns as it will help me keep track if robot has gone around entire room.

Turns = 4;

Now we are facing north and placed on top left corner.

while(turns>0){

If window or wall detected (if window count++) 

Turn Right

Turn--;

While(detection!=wall || detection!=window){

move 1 unit forward

Turn left (if window count++)

Turn right

}


}

I believe in doing so the robot will go around the entire room and count windows and it will stop once it has gone around the entire room as the turns get decremented. I don't feel this is the best solution and would appreciate suggestions on how i can improve my Pseudo-code. I am not looking for any code just a algorithm on solving such a problem and that is why i have not posted this in stack overflow. I apologize if my Pseudo-code is poorly written please make suggestions if i can improve that as i am new to this. Thanks.

  • 2
    The robot doesn't have to know what corner it's starting in; just go any direction until you hit a wall, and then apply your four-corners algorithm. – Robert Harvey May 27 '14 at 0:11
  • Yea you are right actually...do u see other than that how else this can be improved? – user2733436 May 27 '14 at 0:24
  • Don't be so quick to assume there are four walls/corners. You may be better off trying to go clockwise/counterclockwise, keep track of the direction your facing, and positions you have traveled. If you find yourself at a position you've been at before, then you know you've gone all the way around the room. – Jay May 27 '14 at 4:09
  • 1
    In this problem we are assuming the room has 4 walls. – user2733436 May 27 '14 at 4:24
  • If the shape of the room is not known just make to variables xOffset and yOffset. Both set to 0 when you start at the wall. Increase yOffset each time you drive up once and decrease for driving down. Same for xOffset and left/right. If you reach 0/0 again you drove around the room (special case: a corridor with width 1 and you start there). – kufi May 27 '14 at 11:18
3

You need to find the top left corner. Instead, move forward (no matter the current orientation of the robot) until you hit the wall, then turn right. Those are the steps 1 and 2 in the illustration below. At the step 2, the robot turns right, orienting itself to the top.

The second phase is to move forward, constantly turning left to see whether you're near a wall or a window. For example, at step 6, the robot will turn to be oriented to the left, see that it's a wall, and turn back to be able to move to the top. At step 7, the robot turns left, sees that it's near a wall, and can now turn right twice, since it knows that there is also a wall at the top of it. It performs a similar operation at step 16, 23 and 32.

At step 9, it records that it's near a window. At step 10, he knows that it previously had a window at the top of it, so there is no need to count a different window.

enter image description here

The approach supposes that:

  • The room is rectangular. Having a non-rectangular room would require a slightly more complicated approach.

  • There is no walls or windows inside the room itself, i.e. in the middle of the room. Having walls or windows inside a room would require an overly-complex approach where the robot should scan nearly the whole surface.

  • The robot knows that it has already visited a given cell. If it doesn't know that, it should be at least able to know the size of the room.

The algorithm may further be improved, for example by handling the case where the robot touches the wall in its initial position, but I suppose such optimizations are outside the scope of the exercise.

  • Yea good suggestions, other than that do you see how else this algorithm can be improved or would you have more efficient solution? – user2733436 May 27 '14 at 0:25
  • 1
    @user2733436: if you look for something more efficient, you have to be more specific. What are the constraints? What sort of efficiency do you require? – Arseni Mourzenko May 27 '14 at 0:43
  • Yes your solution actually makes more sense. i just wanted to know whether my answer also made sense so that i have an idea of how i am doing with such problem. So please let me know apart from not needing to go to the top left corner was there anything else wrong with my answer. thanks. – user2733436 May 27 '14 at 1:04
  • @user2733436: if I understand your approach correctly, it is the same as mine, except the top-left corner point. – Arseni Mourzenko May 27 '14 at 1:24
  • Yea i decide to go to top-left corner first than i start the counting and decreasing the number of turns until all turns are used up to terminate the main loop.. – user2733436 May 27 '14 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.