Robotics (202-25161) - Spring 2002

1. You are asked to formalize several aspects of the soccer game. As a minimum, define axioms as follows:
   • Location and velocity of the ball (Newton's second law) For simplicity, ignore spin...
   • ``Off-side'', for a certain team.
   • A goal is scored in favor of a team.

   Answers

   • We will use the location predicates below, but exclude the z axis, as it is not used in the simulator. Thus, we have (assuming implicit universal quantifier of all unbound variables, and a discrete time-step dt of 1):

     holds(t, velocity(ball, vx, vy))  <=> holds(t+1, velocity(ball, vx+ax, vy+ay))
     
     holds(t, location(ball, x, y))  <=> holds(t+1, location(ball, x+vx, y+vy))
     
     holds(t, acceleration(ball, ax, ay)) and not abnormal1(t) =>
            holds(t+1, acceleration(ball, ax, ay))
     
     holds(t, kick_action(ball, Fx, Fy)) => 
         abnormal1(t-1) and abnormal1(t) and 
         holds(t, acceleration(ball, Fx/M, Fy/M)) and
         holds(t+1, acceleration(ball, default_ax, default_ay))
     

     Where ball is a constant presumed to be the ball, and the default_ax and default_ay are constant accelerations - we can assume 0 here. To represent friction they need to depend on vx and vy.
   • This depends on the exact definition of "off side". We will use the following simplified definition: a team has a player off side if some player, player1, touches a ball passed by player2 on the same team, and at the time player2 touched the ball there were less than 2 opposing players closer to the opposing team's end of the field than player2. Although not the exact definition, this should do... We will define a fluent closer(team, p1, p2) to denote that p1 is closer than p2 to team's end of the field. Also, we will introduce a counting predicate less-than-2-closer. As before, unbound variables are assumed universally quantified. We assume all players are ON THE FIELD... Additionally, we will have the "off side" hold only momentarily, at the time player1 touches the ball.

     
     holds(t, closer(team, p1, p2)) <=> 
            (holds(t, location(p1, x1, y1)) and holds(t, location(t, x2, y2)) 
            and ((team = team1  and  x1 < x2) or (team = team2  and  x1 > x2)))
     
     holds(t, less-than-3-closer(team, p))  <=>
               ((holds(t,closer(team, p1, p)) and  holds(t,closer(team, p2, p)) and 
                 member(p1, team) and member(p2, team))  => (p1 = p2))
     
     holds(t, offside(team))  <=>
          (exists p1, p2, team1, t1 < t   
             member(p1, team) and member(p2, team) and is-team(team1) and
             not (team1=team) and
             holds(t, touch(p1, ball)) and
             holds(t1, touch(p2, ball)) and
             holds(t1, less-than-2-closer(team1, p1)) and
             not (exists t2, p player(p) and holds(t2, touch(p, ball))
             and t1 < t2 < t))
     

   • Scoring a goal is simpler. We will only need an auxiliary predicate goal-line(team, x,y) which means that a location is just past the team's goal line (defined easily using ineuqlities based on the geometry). We will also need a fluent in-play, so that we do not keep scoring goals if the ball happens to rest in that zone... We get:

     holds(t, goal(team))  <=> 
         (holds(t, in-play) and holds(t, location(ball, x, y)
          and goal-line(team1, x, y) and is-team(team1) and not (team = team1))
     
     holds(t, goal(team)) => not holds(t+1, in-play)
     

2. Assume now that players can see omni-directionally and without error measure the POSITION of everything in the field. The STATE of the world is position, velocity, and acceleration of the ball and all players. Each player can decide to accelerate in any direction, and the accelerate commands work without error and with unlimited velocity or acceleration (unlike the simulator). Assume also that the players do NOT turn but again, can accelerate in any direction.
   • Is the world state as defined here completely observable?
   • Assuming only one agent on the field, that needs to get to the opposing goal within 10 seconds, with a final velocity of 1, with no opposition, is this problem controllable?

   Answers:

   • The world is observable because position is visible and one can compute velocity and acceleration by differentiation. If the system is linear and time invariant (as seen above) we can use the theorem to show the same. For simplicity, we will decompose the state equations according to dimensions (we will show just the X dimension for clarity), and get the following:

     State (X component):     (ax, vx, x)'
     Now, the transition matrix A will be:
               0  0  0
               1  1  0
               0  1  1
     
     And the observation matrix C is:   (0  0  1)
     
     We need to compute the rank of the matrix:
     
          C
          C A
          C A A
     
     The matrix is:
     
          0 0 1
          0 1 1
          1 2 1
     
     Since its rank is 3, the system is completely observable.
     

   • This problem is completely controllable. It is certainly controllable within 10 seconds. To show this, we provide a control that achieves the goal within T>0 seconds. Let d be the distance of the agent to the goal, with components dx and dy. Let the agent have an initial velocity of vx, vy. Our control (acceleration - to get force multiply be agent mass) will be:

     kx delta(0) + k1x delta(T)    in the X dimension, and likewise
     ky delta(0) + k1y delta(T)    in the Y dimension,
     
     Where:
     delta(t) is the dirac impulse function at time t, and
     
     kx = -vx + dx/T
     ky = -vy + dy/T
     
     k1x = -dx/T + 1
     k1y = -dy/T
     

3. Write the following projection axioms:
   • If a player kicks a ball into the opposing goal from a distance of less than 10m, a goal will be scored for his team after a delay of less that 3 seconds.
   • If a player is holding the ball, and moves with it from location 1 to location 2, it will keep holding the ball and both will be at location 2 after the delay required to travel (assume constant velocity).
   • If a player moves without the ball to a certain location, it will get there after the required delay.
   • If a player grabs the ball, it will hold the ball if the player is in the same location as the ball.

   Answers:

   • We will assume a distance function between locations, and a goal_at(Team, X,Y) predicate that is true when X and Y are the location of Team's goal. Note that in the specification we forgot to require that the player has the ball, so we can ignore it in the answer as well (even though this is technically incorrect).

        project(distance(X,Y, X1, Y1) <= 10, 
               kick(P, ball, to_goal(Team)), 
               [0, 3], goal(Team1)) :-
               player(P) and member(P, Team1) and location(ball, X, Y) 
               and team(Team) and team(Team1) and goal_at(Team, X1, Y1).
     

   • Again we can use the distance function, and also we invent a player_speed predicate.

        project(holding(P, ball) and location(P, X, Y),
                move(X, Y, X1, Y1,), 
                V/distance(X, Y, X1, Y1),
                holding(P, ball) and location(P,X1,Y1) and location(ball,X1,Y1)) :-
                player(P) and player_speed(V).
     
     

   • Same as above, but ignore ball.

        project(location(P, X, Y), move(X, Y, X1, Y1,),  V/distance(X, Y, X1, Y1),
                location(P,X1,Y1)) :-
                player(P) and player_speed(V).
     

   • This one is simpler...

        project(location(P, X, Y) and location(ball, X, Y), grab(P, ball), 0,
                holding(P, ball)) :- player(P).
     
4. Finally, we write the plan library and test whether it works.
   • Write a task decomposition axiom: to score a goal, you need to hold the ball, then move with it to near the goal, and then kick (move and kick are primitive).
   • Write task decomposition for holding the ball: be at ball location, then grab the ball (grab is primitive).
   • Write a task decomposition axiom for holding the ball: wait for a pass by a team member.
   • Show a task decomposition for the initial state, where the player is 50 meters from the goal, the ball is 40 meters from the goal (your choice as to exact location), and the task is to score a goal. Show temporal relations after decomposition to primitive actions.
   • Use the projection axioms to show that indeed a goal will be scored by the above plan and decomposition.

   Answers:

   • By scoring a goal, we mean to acieve a goal for a team, thus:

        to_do(achieve(goal(Team)), Interval,
              plan([achieve(holding(P, ball)), move(X, Y, X1, Y1), 
                    kick(P, ball, to_goal(Team1))],
                   [end(1) < begin(2), end(2) < begin(3)],
                   [protect(end(1), begin(3), holding(P, ball)),
                    protect(end(2), begin(3), location(P, X1, Y1))]) :-
              player(P) and team(Team) and team(Team1) and not (Team1=Team) and
              holds(begin(2), location(P, X, Y)) and goal_at(Team1, X2, Y2) and 
              distance(X1, Y1, X2, Y2) < near_goal_threshold.
     

   • This is simpler, apparently, but note that the ball may be moving, making this more challenging!

        to_do(achieve(holding(P, ball)), Interval,
              plan([achieve(location(P, X, Y)), grab(P, ball)],
                   [end(1) = begin(2)]) :-
              holds(end(1), location(ball, X, Y)).
     

   • This is MUCH simpler...

        to_do(achieve(holding(P, ball)), Interval, wait_for_pass).
     

   • The easiest decomposition is: the achieve(goal(Team)) is decomposed into:

     achieve(holding(P, ball))
     move(X, Y, X1, Y1)
     kick(P, ball, to_goal(Team1))
     

     Temporal ordering is unique. Now, there are 2 possibilities to decompose achieve(holding(P, ball)): either wait for a pass, or the plan to move to the ball and grab it. The former decomposition succeeds, but since we do not have a project axiom for wait_for_pass, we will FAIL to prove that a goal is scored! So, we need to use the other decomposition, achieve(holding(P, ball)) into:

     achieve(location(P, X, Y))
     grab(P, ball)
     

     Actually, we now have a problem as there is no way to decompose the former - but let use use the decomposition to the primitive move(X1, Y1, X, Y) (i.e. assume we have this to_do axiom). We now have a complete plan, and need to show that it can work. Assume that (with x axis in a line connecting middle of goals):

     holds(T, location(p1, 50, 0))
     holds(T, location(ball, 40, 0))
     

     Now we have a problem, as we do not know the location of the ball at the after the move! However, if we assume a ball initially stationary, and stays so unless moved by player, we get the final task decomposition into the actions (assuming "near goal" is 10):

     move(50, 0, 40, 0), grab(P, ball), move(P, 40, 0, 10, 0), 
     kick(P, ball, to_goal(other_team))
     

   • Now we try to use the project axioms to prove a goal. This should work, because project places te player at (40, 0) after the move (at time 10/player-speed). Now, assuming tasks are executed emmediately one following the previous, the grab is executed at that time. The ball did not move (necessary new project axiom!), and grab results in holding the ball. Then the second move takes player and ball to (10, 0), and the project also has player holding ball at that time (40/player-speed). Then the project over the kick axiom states that between 0 and 3 seconds later, a goal is scored. Thus, we can show that a goal will be scored sometime between 40/player-speed and 40/player-speed + 3.

Deadline: Tuesday, April 30, 2002

Suggested Predicates to Use

It is heavily suggested that you use the following predicates (in addition to the standard predicates, such as equality, the ``holds'' relation, etc.). Otherwise, you will have to invent your own, which is MUCH harder... Use constants of your choice, such as for the team names, etc.