Robot and the Wall

Consider this puzzle as "in test mode" now, please, and don't hesitate to report issues at forum.

It so happened that I recently participated in some local "robot programming" challenge and while the event was plagued with numerous issues, it inspired a few ideas which could make exercises of some interest for us.

The first task was about driving a robot (small wheeled vehicle) over the predefined room with some obstacles - always in the same, predefined configuration. This sounds easy - we seemingly can hard-code some trajectory, giving certain commands to the robot at certain moments - however control is subject to slight inaccuracies which, over the time, may lead to error in position significant enough for the robot to miss the target space. The video above shows my solution with robot driving backward all the time to save the time.

One of the approaches to amend this is to correct robot's position from time to time. Particularly useful trick would be to learn how to approach the wall and drive parallel to it at some specific distance (in the task mentioned, for example, it is convenient to drive over the "bridge" between two rooms in this manner, so the robot will leave the bridge at certain point even though it enters bridge with some uncertainty of angle and coordinate).

Details

You may find the task Socket Server helpful if you don't feel confident enough with UDP - but on the other hand it is so simple that you can learn it on just here and now.

Robot has some internal program which we will refer as "controller". It can accept your commands via UDP network protocol - and it provides "telemetry" data at intervals - also over the UDP. It is internal network so the packets travel very fast, but still it is a kind of asynchronous control. Each command is just two integers separated with space v and w - of them the first is the wanted linear speed, i.e. the speed with which you want the robot to move forth, while the second is the wanted rotational (angular) speed. The first is in millimeters per second, the second is in milliradians per second.

Use port 9000 to send commands.

Both speeds however won't set immediately - engines have some inertia - thus the speed change is limited by certain acceleration. Linear acceleration do not exceed 0.1 m / s^2 in absolute value and angular acceleration do not exceed 0.4 rad / s^2 in asolute value. For example, if you give command 1000 0, the speed reaches 100 by the end of the first second, 200 by the end of the next second and so on, until 1000 is reached by the end of 10-th second and won't increase further. One special command is the single word done - you should send it when you decide the goal is reached, so that controller program will finish and report the result (the robot should be moving full-speed forward parallel to the wall at the requested distance).

Initial position is not very far from the wall (somewhere around 1 metre) and robot is less or more aligned with the wall (so that at least on the right lidar should see the wall). Both initial speeds are zero.

"Goal" distance is passed to your script via the first command line argument. e.g. in Python you should be able to get it as:

goal = int(os.argv[1])

As about telemetry, robot's main instrument is lidar - a kind of laser range-finder which detects distances to obstacles in some sector in front. In our case it is convenient to imagine that 91 rays are cast with the step of 1 degree, of them the middle one spreads straight forth, the first one at 45 degrees to left and the last one at 45 degrees to the right.

Telemetry packet consists of 94 integers in total, space separated:

time cur_v cur_h lidar[0] lidar[1] ... lidar[90]

The first is a "timestamp" from the start of simulation (milliseconds), next follow current achieved linear and angular speed, and then lidar values array, for example:

11010 500 100 9000 9000 9000 ... 2334 2286 2242 2199 2159 2121

this means 11.01 seconds, 0.5 meters per second, 0.1 radians per second (positive means turning left) and lidar values follow also in millimeters, with 9000 being maximum value (lidar reports it when the ray don't hit any obstacle).

Listen at port 9001 for telemetry. The first telemetry data are sent as soon as controller starts and it is expected to start immediately after your own program starts - though the order is not 100% guaranteed this shouldn't be a big issue, your robot simply can rest until receiving the first telemetry record.

That's all. Input and answer boxes below are provided only for convenience (you can use them to test some code with "Run" button as usually), but actually your code is checked. It should be written in one of the languages supported by our "sandbox".

We have several pieces of code prepared to help you in this page with 3 files:

• testprg.py example of the "robot" program in Python, which properly receives telemetry and sends commands - but doesn't solve the problem (instead it turns to the wall and drives almost straight to it
• ctl3.py - "controller" code in Python, similar to that which is used by the checker (but enhanced to provide more debug information on the run) - of course it should be run simultaneously with "robot" code (but the robot code given above waits for telemetry so could be launched earlier)
• ctl3-prg.py - combination of two programs given above, so that they are executed simultaneously (using os.fork()) and you can copy-past them to our "Sandbox" and execute there for debugging. Put attention to TIME_SCALE and TIME_STEP parameters.

Don't use sleep(...) however as the simulation on server side is sped-up several times!

You should have upto 12 seconds of simulated time before the timeout. Don't forget to send done command when done (and exit your program). Other success criteria:

• robot should move at least at 95% of full speed by the end
• goal distance from the wall should have no more than 0.01 error (1 centimetre)
• it should move parallel to the wall with the angular error no more than 0.02 radian
• it should have zero angular speed (at least no more than 0.01)

Below is a small "trajectory visualizer" - you may use it while testing. As soon as "answer" area gets some data, its lines are parsed and any of them which contains fragments like X=... and Y=... is treated as a trajectory point to be drawn in this field. For example if you copy-paste the sample program mentioned above into "solution" area and hit the "run" button, you should soon see the red trajectory here. Alternatively you may simply copy-paste your own debug output there.