Homework 5 (S2 2022)

This is the fifth homework assignment. Your goal in this assignment is to write a function that solves a simple problem which, if extended, may have useful and important applications in various fields.

Your solution to this homework will also be marked on code quality. This means some part of the marks will be given for good code organisation, variable/function naming, and commenting. The marks for code quality are distinct from those for functionality; to gain full marks, your submission must be both functional and readable.

Postmortem discussion#

The analysis is available in the bottom of this page and the solution code with an extended test suite in chase_sol.py.

Practical information#

The assignment is due Monday the 3rd of October at 9:00am (Canberra time). This is the Monday in semester week 9.

To submit your solution, you will upload a single Python file via Wattle. Here is the assignment submission link.

In addition to submitting your solution, you must attend the following lab (in week 9). In the lab, your tutor will ask you some questions about your solution, and give you feedback if there is anything you need to improve. This discussion with the tutor is also part of the assessment.

If you fail to show up for the discussion with the tutor, you will receive zero marks for this assignment. If you do not submit a solution, you may still get partial marks if you are able to show the tutor that you have made some attempt to solve the homework.

The homework is individual. You must write your own solution, and you are expected to be able to explain every aspect of it.

As usual, you should have followed last week’s lectures and worked through the exercises in lab 6 and lab 7 before starting on the assignment. The assignment should not take more than two or three hours to complete. The pre-programming analysis, the one you perform before starting to write code, will probably be more important then code writing itself.

Disclaimer#

Any reference to harm done to animals is purely fictitious. We do not approve of hunting any animal for sport or pleasure.

The problem#

A hare is running in a straight line with a constant speed. It is being chased by a hound, which always runs towards the hare. The hound’s speed is also constant. The problem is whether — given the direction and speed of the hare, the distance between it and the hound, and the speed of the hound — whether the hound will be able to catch the hare in a specified amount of time. That’s it!

If you have studied calculus you may know that this problem has an exact mathematical solution. But if we make the problem a bit more complex (allow the hare to veer off course, or an error which the hound has in homing in on the hare), the problem becomes too difficult to solve analytically. Our simulation algorithm used to solve this problem will be useful for solving a more difficult and perhaps more realistic one.

This homework will ask you to write a function

chase(target_speed, chaser_speed, chaser_pos, max_steps, catching_dist=1e-5)

which takes as arguments:

1. target_speed – a float representing the target’s speed in metres per time step; because we can change the coordinates using rotation and translation, the actual direction of the hare velocity is not necessary to define, only its absolute value matters; in other words, we are using the coordinates in which the hare always runs in the horizontal direction, along the x-axis (y=0), left to right (as shown on the Figure), it starts at the point (0, 0).
2. chaser_speed – a float representing the chaser’s speed in metres per time step
3. chaser_pos – a tuple representing the (x,y) position of the chaser at the start of the chase; x and y are floats and are in metres
4. max_steps – an int representing a maximum number of time steps during which the chaser is able to pursue the target; the pursuit may terminate earlier if the target is captured
5. catching_dist – is a float representing the distance which determines whether the chaser has caught the target – if the separation between the two becomes smaller than catching_dist then the chase is successful

and returns the boolean value indicating success (True) or failure (False) of the chase within the max_steps.

Note 1 target_speed and chaser_speed, despite their name are actually measured in metric units, the same as distance (ie, in metres). Hence you can add position coordinate (x and y) with either of these speeds. Think of them as distance which an object moving with a physical velocity v will cover in the time interval \(\Delta t,\) the very same time interval which is implicit in the time step of the discrete movements we use here to approximate the continuous flow of time.

Note 2 As well as the catching_dist indicating a capture at the end of a time step, the chaser can also capture the target between time step updates. This can happen if their paths cross during the time step. Therefore, it is important to check if the two objects get within the catching distance catching_dist of each other at all times, not just at the discrete times when the pursuer adjusts its speed direction.

Assumptions and restrictions:

• The function must return a boolean value.
• The initial position of the target is at (x=0, y=0) and it always travels East ie. x increases, y remains 0.
• At the beginning each time step the positions of the target and the chaser are recomputed.
• The chaser is smart! It knows that at the beginning of each time step if it heads towards the current position of the target, then the target will move during the time step and might never be captured Instead, at the beginning of each time step the chaser heads towards the position of where the target will be at the end of that time step.
• The last parameter, catching_dist is a default value parameter; one can pass a different value for it, but if not given it is the value which is used.

Template file and hints

As a starting point, we provide you with a skeleton code file: chase.py. Download this file and write in it your implementation of the function.

In the template file you will find we have already defined four functions to help you solve this problem:

• advance_position(r, v) calculates the next position of an object (target or chaser) based on its current position r and its velocity; both r and v are (x,y) tuples.

• check_contact(r1, r2, tol) checks if the two points r1 and r2 are separated by a distance smaller then tol.

• get_chaser_direction(chaser_pos, target_pos) calculates direction of next chaser move based on its current position, and position of the target (all positions are (x,y) tuples).

• def chaser_crossed_target(chaser_pos, next_chaser_pos, target_pos, next_target_pos) which can be used for “on the flight” checks (see explanation below).

The template file contains an from math import ... statement — you may use functions from this package in your code. You must not import any other modules.

Testing#

The skeleton file has two testing functions: test_chase_1() and test_chase_2(). They run some tests on chase function, and will raise an error if any of the tests fail. If all tests pass, the testing function prints the message “all tests passed” at the end. The first test function uses low precision for catching_dist, and the chaser() function implementation which checks the catch condition only at the end of time step will pass it. The second test function checks special cases when the target and the chaser are on the same line, and the result of the chase depend on the mutual speed, initial separation and the maximum number of steps. If you want to test your solution against higher precision, you can define more test functions which are passed an appropriate value of catching_dist parameter. To pass such tests, you need to consider the possibility of “catching on the fly” when the distance between the target and the chaser gets smaller than catching_dist between the time steps at which the chaser adjusts the direction of its speed. You may use the function chaser_crossed_target() or define a function(s) of your own to perform these “on the fly” checks. This is a more difficult problem, which you need to solve to get the top mark.

Remember that testing only checks a small number of predefined cases; it can never prove that your function works correctly for all valid arguments. You should examine the test cases that are provided, and think about whether there are any important ones that are missing.

Note that you can define additional functions, if you think it helps you decompose the problem or write a better solution. Your function definitions should contain docstrings, but you may not use strings as comments anywhere other than on the first line inside a function, or at the beginning of the file.

Marking#

Code quality

In this homework (like in the last one) we will also be marking your submission for its code quality. This includes aspects such as:

• Using good function, parameter and variable names. The names of some functions in the homework are fixed, but if you define additional functions (to decompose the problem) then they should be given descriptive names.

• Appropriate use of comments and docstrings. This means not too little comments, but also not gratuitous, useless or incorrect commenting.

  This means not too little comments but also not too much. Comments should be accurate, relevant, and readable. A docstring should appear as the first statement in every function definition.

• Good code organisation.

  This includes appropriate use of functions to decompose a problem and avoid code repetition. Also, do not import modules that you do not use.

What to submit

You should edit the skeleton file chase.py, then upload only this file with your implementation of the function using the assignment submission link on Wattle.

Remember that you must upload a single Python code file. Do NOT zip it or convert it to another format.

The file that you submit must meet the following requirements:

• It must be syntatically correct Python code.
• Like the file you downloaded, it should contain only function definitions, and, optionally, import statements. However, it is not necessary to use any module to solve the problem, and you should only import modules that you actually use. Comments, including docstrings (if they are used appropriately) are of course OK to include. Anything that is not a function definition or import statements will be ignored when we check your submission.

As mentioned above, you must also attend the following lab and answer your tutor’s questions about your solution. This discussion is part of the assessment. You should be prepared to answer or demonstrate to the following questions:

• Can you download the file that you submitted from wattle?
• Can you run that file in the Python interpreter (using an IDE of your choice)?
• If the file has syntax errors, can you use the error messages from the interpreter or IDE to identify where the syntax errors are?
• Does your submitted file meet the requirements stated above? Does it contain anything that is not a function definition? If so, can you point it out?
• Does your implementation pass all the tests run by the unmodified testing functions?
• Is your implementation correct for all valid arguments?
• Does your function always return a value of the correct type?
• Did you think of any other test cases that should be used to test the function, in addition to or in place of those provided?
• What is the difference between the print function and the return statement?

In marking this assignment we will consider the following:

• Does your submitted file satisfy the requirements specified above?
• Does your implementation compute the correct value for all valid arguments?
• The quality of your submitted Python code, including its organisation, naming and documentation (with docstrings and comments).
• Your ability to use the tools (e.g., the IDE or Python interpreter), your understanding of Python’s error messages, and your understanding of the solution, as demonstrated in your discussion with the tutor.

The assignment is worth 4% of your final mark. 2 marks are based on the functionality of your submission, and 2 marks on the quality and readability of your code.

Homework Five Postmortem#

Problem Analysis#

The problem in Homework Five has originated from Physics. As a continuous time problem it has an elementary yet elegant solution. For example, the chaser trajectory, when the chaser starts at \(\boldsymbol{r}=(0, -L)\), is described by this equation (in the polar coordinates \((r, \varphi)\)):

where \(V\) is the chaser speed, and \(u\) is the target speed. The trajectory is written in the target reference frame where the target is at rest in (0,0), and the chaser gets an additional velocity component \((-u, 0)\), which explains why trajectory first leans to the left (see the Figure below), because the chaser runs leftwards at the beginning. The black curve describes the case \(V = 2u\), the blue \(V=1.25u\) and the red \(V=1.05u\).

Similarly, one can compute the time needed for the chaser to catch the target:

Solution#

When being solved numerically, the problem is considered in discrete time, and in the simplest version (which was offered to you as Homework Five) the time intervals are constant. This makes the problem different from the continuous time original, and new effects can appear in a solution, which (being formally correct) can display non-physical oscillatory movements of the chaser around the line of target run. To remove such effects, an adaptive scheme can be used, when the chaser adjusts its velocity at time intervals which depend on the distance to the target. One consequence of such oscillatory movements, which occur when the chaser speed is too high, is inability for the chaser to catch the target (which is impossible in the continuous problem). Such peculiarities can produce undesirable results in the solution testing, something we experienced in our marking process. Therefore, to preserve marking fairness and integrity, we accepted as correct the solution which truthfully implemented the algorithm of homing, even if the motion described by such solutions did not yield the correct result (like catching the target in a situation when catching is guaranteed in the continuous time).

Let’s briefly describe the approach of implementing the algorithm (which is different from the one you were advised to follow). The key part here is to check the close contact not only at the end of time intervals, when the chaser adjusts its velocity, but also during the time interval when it moves in a fixed direction. There are two possibilities, “a slow chaser” and “a fast chaser”, and the distance at which the rendezvous happens is computed differently. The Figure illustrates the way how the two distances are defined, and the solution has necessary calculation details.

This is the code for the function min_passing_distance which calculates the distanse d:

def min_passing_distance(r1, v1, n1, tau = 1, r0 = (0,0)):
    '''hound's path form r1 with absolute velocity v1 in the
    direction n1 over the time interval in (0,tau) with hare 
    at rest in r0 (as happens in the hare reference frame); 
    what is the minimal separation distance the two can be at?
    '''
    # P is the closest point on the hound path to r0 (hare's position)
    delta_r = diff(r0, r1)
    l = abs(_dot_prod(delta_r, n1))     # distance from P to r1
    l1 = tau * v1                       # length of full path (before, on and after P0)
    d = abs(_cross_prod(delta_r, n1))/2 # length of the normal from r0 to P
    if l1 >= l:  # the hound will pass through the closest point (normal base)
        return d
    else:  # the hound will stop short of the point P 
        return sqrt((l-l1)**2 + d**2)

The functions _dot_prod and _cross_prod calculate the length and the height of projections from the chaser starting point to the target position.

The main function chase is implemented with min_passing_distance in a bit long but straightforward way:

def chase(target_speed, chaser_speed, chaser_pos, max_steps, catching_dist=1e-5, tau=1):
    '''
    the usual docstring blah...

    The special cases to improve performance and cut corner cases:
    General condition -- the target and chaser are aligned, ie, chaser_pos[1] = 0
    1. chaser is behind at the start AND fast target (target_speed >= chaser_speed):
       False (always)
    2. chaser is behind at the start AND slow target:
       True OR False depending on available time (max_steps)
    3. chaser is ahead at the start:
       True OR False depending on available time
    '''
    if chaser_pos[1] == 0:
        if chaser_pos[0] < 0 and target_speed >= chaser_speed: # slow chaser
            return False
        separation = abs(chaser_pos[0])
        delta_s = chaser_speed - target_speed if chaser_pos[0] < 0 else chaser_speed + target_speed
        return ceil(separation/delta_s) <= max_steps
    # generic (non-aligned) case -- condition for T and C having equal velocities not possible
    # and the chaser movement direction (normalised velocity) is defined
    tp = (0, 0) # target starting position 
    V  = target_speed
    tv = (V, 0) # 2-tuple of target velocity
    cp = chaser_pos
    if has_contact(tp, cp, tol=catching_dist):
        return True
    for i in range(0, max_steps + 1):
        n, next_cp = get_next_chaser_params(cp, chaser_speed, tp, V, tau)
        cv = (n[0]*chaser_speed, n[1]*chaser_speed) # chaser velocity
        # transfer into the target reference frame to check the contact during next step
        cv = galilean_transfom(cv, tv) # chaser velocity transform, target is at rest now
        cs = sqrt(cv[0]**2 + cv[1]**2) # chaser speed in moving reference frame
        # print(f'chaser position {cp} in rest RF')
        cp = (cp[0] - tv[0]*i*tau, cp[1] - tv[1]*i*tau) # chaser coordinate transform, target is at (0,0) now
        # print(f'chaser position {cp} in moving RF')
        if cv[0]**2 + cv[1]**2 == 0: # target and chaser move with the same velocity -- chased is doomed to fail
            # print(f'target and chaser do not move relative to each other, give up')
            return False
        d = min_passing_distance(cp, cs, norm(cv))
        # print(f'min passing distance {d} at step {i}')
        if d < catching_dist:
            return True
        else: # didn't catch, reset for the next step (in the rest reference frame)
            cp = next_cp # chaser starting position on the next step
            tp = advance_position(tp, tv) # target starting position on the next step
    return False

At the beginning, the special case of aligned chaser and target is considered (which was tested in test_2 of the original chase.py); this part can be regarded as optimisation trick, when the function result can be obtained by a different and faster computation. The rest is a direct implementation of the catching distance condition. The full solution contains a number of helper functions (including those which were included in the template file). Find it here chaser_sol.py.