Robot Simulator and Turtle Graphics, Revisited

This is an update to last week’s post about using VPython to make a robot simulator.  Last week, the vturtle.py module was really just a fancy turtle graphics engine.  The robot could move around and leave a drawing trail, but it could only dead reckon because it didn’t have any sensors.

This week, I added the ability to create obstacles for the robot, in the form of walls… or other robots.  The robot can now “bump into” things, with a stall sensor indicating when its movement is impeded.  You can also add proximity sensors, with configurable range and mounted in configurable locations around the circumference of the robot chassis.  (As before, everything is modeled after the Scribbler; I experimented with the real thing to come up with a reasonable default setup, which includes three sensors looking left, front, and right, with about 10 cm range.)

You can download the updated version at the usual location.  Here is a screenshot of a simple demo with the robot “wall-following” a maze:

The vturtle robot wall-following through a maze.

Admittedly, much of the motivation for this project stemmed from its utility for students learning about programming.  Working with the Scribbler itself is a lot of fun, but it is not always available (e.g., when the students are not in the classroom), and even when it is, it can be a little flaky at times.  This simulator allows students to experiment with pretty complex robot behavior any time, anywhere they have a computer.

But there was another reason I found this project interesting.  There is some nice mathematics involved in the collision detection and proximity sensing, some old hat, some new to me.

All of the sensor-related computation involves detecting the intersection between:

  1. Two circles, when the robot collides with another robot;
  2. Two line segments, a proximity sensor beam and a wall; or
  3. A circle and a line segment (more on this later).

The first case is the simplest; just compare the distance between the robots with the sum of their radii.  The second case is more involved, and is perhaps the most elegant, but is a pretty standard computational geometry problem.

The third case, the intersection of a circle and a line segment, was one I had not investigated before, and occurs in two situations: when a robot collides with a wall, or when a robot’s proximity sensor beam intersects another robot.  The general problem is shown below:

circle_line

Intersection of a circle and line segment.

Given a line segment XY and a circle centered at C with radius r, we want to determine if the two intersect.  Representing points with corresponding vectors, we can parameterize points on the line segment with:

\mathbf{p}(t) = \mathbf{x}+t(\mathbf{y}-\mathbf{x}), t \in [0,1]

An intersection occurs when a point on the line segment is also on the circle; that is, when \mathbf{p}(t) is distance r from \mathbf{c}:

\left|\mathbf{x}+t(\mathbf{y}-\mathbf{x})-\mathbf{c}\right| = r

Letting \mathbf{v}=\mathbf{x}-\mathbf{c} and \mathbf{w}=\mathbf{y}-\mathbf{x}, we can express this condition more efficiently without the underlying square root operation as:

(\mathbf{v}+t\mathbf{w})\cdot(\mathbf{v}+t\mathbf{w})=r^2

This expands into a quadratic in t,

a t^2 + b t + c = 0

where

a=\mathbf{w}\cdot\mathbf{w}

b=2\mathbf{v}\cdot\mathbf{w}

c=\mathbf{v}\cdot\mathbf{v}-r^2

So there is an intersection iff this quadratic has a root in [0,1].  See the vturtle.py code for an example implementation.

Finally, following is example source code for the maze demo screenshot above:

import vturtle

# Create robot on a walled tabletop.
robot = vturtle.Robot(obstacles=vturtle.maze(rows=5, columns=5, cell_size=40))
robot.pen_up()

robot.fast_forward(5)

# Move until we find a wall.
while not robot.sensor(1):
    robot.forward(3)

# Wall-follow, keeping a wall on our right.
robot.left(90)
while True:
    while not robot.sensor(1) and robot.sensor(2):
        robot.forward(3)
    if robot.sensor(2):
        robot.left(90)
    else:
        robot.forward(15)
        if robot.stalled():
            robot.backward(3)
        robot.right(90)
        robot.forward(20)
This entry was posted in Uncategorized. Bookmark the permalink.

4 Responses to Robot Simulator and Turtle Graphics, Revisited

  1. Pingback: Yet Another Rubik’s Cube | Possibly Wrong

  2. Lana Pereira says:

    I have been using Squeak and Smalltalk to teach my middle school students to program virtual robots, and I love it. I have just started learning Python via Udacity, and this simulator is far better because it includes the obstacles, so I will have to take a serious look at it.

    Thanks a lot,
    Lana

    • Great! Let me know if you encounter any problems or annoyances using it. The simulator started out as just an experiment, but in the past year it has proved to be an environment that the students seem to really enjoy. Just in the last couple of weeks, we have added some additional interesting twists: we are using the PyGame module to get input from a joystick (in our case, wireless Xbox 360 controllers), and the students’ first idea was to combine that with this VPython-based simulator, and use the joystick input to drive the robot. Much fun ensued.

  3. Pingback: Hunt the Wumpus | Possibly Wrong

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s