\documentclass{article}
\usepackage[review]{acmconf}
%\input macros.tex

\usepackage{array}
\usepackage{epsfig}
\usepackage{alltt}
\usepackage{fancybox}
%\usepackage{psboxit}

\newcommand{\ang}[1]{\ensuremath{#1^{\circ}}}
 
\title{Robust Action Under Variable Uncertainty: An Algorithm for Robotic Soccer} 
\author{Elly Winner and Manuela Veloso\\
Computer Science Department\\
Carnegie Mellon University\\ 
Pittsburgh, PA 15213 \\ 
\{elly,veloso\}@cs.cmu.edu\\ 
http://www.cs.cmu.edu/\{\char"7E elly,\char"7E mmv\} 
}
 
\begin{document} 
 
\maketitle 
 
\begin{abstract} 
     The robotic platform provided by Sony for the \mbox{RoboCup-99} robotic
     soccer competition brought with it many exciting challenges. The
     quadruped legged robots are fully autonomous, so must have onboard
     vision, localization and control. The challenge we addressed was the
     robust and sensible control of the robot through dynamic changes in the
     accuracy of the information produced by the localization module. This
     paper presents our approach and contributions to these issues. We
     developed a two-constraint system to make the most of the robot's
     control over its localization information. We wrote a basic algorithm
     for scoring goals that does not rely on localization information. We
     developed several localization-dependent performance
     enhancements. We built a mode-based architecture that allows the
     robot to upgrade and degrade its performance without significantly
     affecting its behavior. And we have devised several special algorithms
     to deal with times when urgent action is needed and the robot cannot
     spend time collecting information about its location, and to make the
     most of the basic localization information the robot can use in those
     situations. Our team of Sony legged robots, \mbox{CMTrio-99}, won all
     but one of its games in \mbox{RoboCup-99}, and was awarded third place
     in the competition.
\end{abstract}


\section{Introduction}

     All teams in the \mbox{RoboCup-99} legged robot league use the
     same hardware platform: the Sony quadruped legged
     robots~\cite{sony-robocup99-france}. The robots are completely
     autonomous, with onboard cameras rather than global vision. They
     have an onboard processor to provide image processing,
     localization and control, and are not remotely controlled.

     The game consists of two ten-minute halves, each begun with a
     kickoff. After each goal, the game begins again with another
     kickoff. In the kickoff, the ball begins in the center of the field,
     and each team may position its robots on its own side of the field.

     Each team consists of three robots. Like most of the other teams, we
     subdivided our team into two attackers and one goaltender. Most of the
     remainder of this paper will discuss our work on the attackers.

     The regulations of the \mbox{RoboCup-99} legged robot league specify
     that the field be 2800mm in length and 1800mm in width. The goals are
     centered at each 600mm wide and 300mm tall. Six unique landmarks are
     placed around the edges of the field (one at each corner, and one on
     each side of the halfway line) to help the robots localize themselves
     on the field. The landmarks are 200mm off the ground and 200mm high.
     Figure~\ref{field} shows a sketch of the playing field

\begin{figure}[htbp]
  \begin{center}
    \epsfig{file=field.eps,width=1.0\columnwidth}
    \caption{
      %
      The playing field for the \mbox{RoboCup-99} Sony legged robot league.i
      %
      }
    \label{fig:btw}
  \end{center}
\end{figure}

	
%     We defined the origin of the field to be the center point, with
%     positive length towards the blue goal and positive width towards the
%     left of the blue goal. Angles start at zero (directly towards the blue
%     goal) and are positive in a counterclockwise direction.

     Other members of the \mbox{CMTrio-99} team wrote: a vision system
     which reports which objects are seen, with what confidence, and
     at what direction and distance~\cite{icra00-jim}; and a
     localization algorithm which reports the robot's coordinates on
     the field, along with the confidence of this
     estimate~\cite{icra00-scott}.

     Because the vision system is very reliable and not very speculative, we
     assume that the information it sends about the objects in the world is
     correct. For the remainder of the paper, when we discuss the robot's
     information about the world, we mean its information about its
     location, which is much more speculative.

     Our work is on the behavior of the robot. This problem is especially
     difficult in this domain, in which not only does the robot need to act
     under uncertainty, but it needs to be ready at all times to accept and
     fully use more complete information than it currently has, and to
     gracefully degrade its performance when less information is
     available.

     The robot also has some control over its knowledge of the world: in
     order to learn more about where it is, it can spend more time looking
     around. Although having more information helps the robot tremendously,
     soccer is time-critical, so every moment spent looking around is lost
     time. The other team's robots can use also the robot's
     inattention to their advantage.

     Our strategy includes an architecture that allows the robot to upgrade
     and degrade its performace quickly and gracefully, behaviors that are
     reasonable even when the robot does not know where it is, and several
     special localization-dependent behaviors which dramatically increase
     the robots' efficiency.

     Our team of Sony legged robots, \mbox{CMTrio-99}, won all but one
     of its games in \mbox{RoboCup-99}, and was awarded third place.

     The remainder of this paper is organized as
     follows. Section~\ref{sec:control} presents our scheme for balancing
     the benefit of accurate localization information with the time needed
     to achieve it. Section~\ref{sec:lost} presents our algorithm for
     scoring goals without any localization
     information. Section~\ref{sec:upgrade} presents the methods we use to
     allow the robot to upgrade and degrade its performace gracefully as the
     availability of information changes. It also presents the
     localization-dependent performance enhancements we
     implemented. Section~\ref{sec:urgent} describes some of the special
     cases for which the balance between localization and action described
     in Section~\ref{sec:control} no longer apply, and the algorithms we use
     to deal with this. Section~\ref{sec:results} describes the results of
     tests we ran to determine the optimal localization
     strategy. Section~\ref{sec:conclusion} concludes the paper.

\section{Control over Knowledge}
\label{sec:control}

     In this domain, the robot has some degree of control over its
     knowledge. If its information about its location is poor and it stops
     to look for landmarks, then its information will probably
     improve. However, it is undesirable for the robot to be looking for
     landmarks so often that the frequent interruptions interfere with its
     ability to act. Because robotic soccer is a time-critical game, it is
     also undesirable for the robot to stop and look around when it is not
     necessary to do so--not only because this wastes time, but also because
     whenever the robot isn't paying attention to the game, its opponents
     have a chance to act unimpeded.

     One might conclude from this that the robot should localize itself very
     infrequently, if at all. However, the benefits of accurate localization
     are significant--when the robot's localization information is good, it
     is able to score goals much more quickly then when it is not.

     We present a scheme that balances the time required to get good
     localization information with the benefits this information
     provides. The basis of this scheme is for the robot to localize only
     when it will significantly boost performance.

\subsection{Localizing the Right Amount}

     We found that if we allowed the robot to stop and look around every
     time its localization information fell below a ``useful'' level, it
     spent most of its time looking around. However, if we reduced the
     requirements of ``useful'' localization information to the point that
     it acted for a reasonable amount of time before looking around, then
     its localization information was almost never good enough to use.

     We use a system of two constraints to force the robot to act for long
     enough while also requiring that its localization information is good
     enough to use.

\paragraph{Constraint 1--Enforcing Action:}

     The first constraint is that the robot spends enough time acting before
     it looks around for localization information. If it does not spend
     enough time acting, then its frequent stops disrupt its ability to
     continue its action. For example, if it is trying to push the ball
     towards the goal, stopping to look for landmarks too often causes it to
     lose track of the ball frequently, and to have to stop again to look
     for it. All this stopping and searching not only costs the robot time,
     but gives its opponents time to make strategic plays without its
     intervention.

     On the other hand, if the robot does not look around often enough, it
     loses the opportunity to get and use valuable localization
     information. It wastes time staying in one place, waiting to see the
     goal instead of actively moving the ball in the right general
     direction. This relative inactivity while waiting to see the goal gives
     the opponent plenty of opportunity to notice the ball and try to move
     it towards the opposite side of the field.

     Our scheme uses a counter to require the robot to act for a specified
     amount of time before looking for landmarks. The amount of time the
     robot must act before looking is invariant--it does not depend on how
     bad the robot's localization information is, or how important that
     information is currently. Our scheme requires that the robot act for
     the time it takes the image module to proccess 350 frames of data. We
     chose to count the time in image frames processed by the vision module
     because this information is immediately available to the control module
     (each processed frame invokes an update in the control module), is
     relatively constant per unit time, and does not involve a system call.

\paragraph{Constraint 2--Less Accurate Localization:}

     The second constraint is how accurate we demand the localization
     information to be. If it is good enough, the robot should not stop to
     look for landmarks, but if it is not good enough, the robot should not
     use it.

     It is not immediately obvious how good our localization information
     must be before it is usable. Clearly, if our demands are too high, the
     robot will rarely be able to use the information it has gathered. And
     if they are too low, it will use information that is so inaccurate as
     to be useless at best, and damaging at worst.

     Our scheme specifies that a ``good'' localization estimate of $\theta$,
     or the angle of the robot on the field, have a standard deviation of
     $\ang{30}$ or less. A ``good'' localization estimate of X and Y, the
     coordinates of the robot's location on the field, must have a standard
     deviation of less than 600mm.

\subsection{Avoid Unnecessary Localization}

     One of the best ways of finding a balance between localization
     information and time spent to acquire it is simply to avoid localizing
     when it is not necessary. We have identified two times when it is
     unnecessary: when the robot does not know where the ball is, and when
     it has lost sight of the ball. Our scheme allows the robot to act
     intelligently but does not rely on localization information in either
     of these situations.

\paragraph{Random Search:}

     When the robot does not know where the ball is, it must wander the
     field to search for it. We use a random search algorithm that does
     not rely on localization information. Until the robot sees the ball, it
     alternates between walking forward a random amount and turning a random
     amount.

     Our algorithm does not allow the robot to recognize that it is running
     into a wall or to walking into a goal. Because the vision module does
     not recognize walls, the former would be difficult to add. We did not
     add the latter because of time constraints, but it could easily be
     added.

     Even without these improvements, we found that the random search
     algorithm allows the robot to cover the field more quickly, on average,
     than does a comparison scheme we built in which the robot attempts to
     walk a circuit of the field. This is because ``oriented'' searches,
     like the circuit, require the robot to have accurate localization
     information. To have such accurate localization information, the robot
     must frequently stop and look around, which takes time.

     Localization information thus clearly does not help the robot to devise
     a more efficient path around the field. And, since the ball is no more
     likely to be in one segment of the field than in another, the
     localization information also does not help the robot decide the best
     way to move initially. Therefore, we do not allow the robot to attempt
     to localize itself while searching for the ball, nor do we use any
     information the robot already has about its localization to influence
     its search behavior.

     A final benefit of the random search algorithm is that the robot will
     always be able to find the ball, given a long enough time, as long as
     the obstacles between it and the ball are navigable. For every fixed
     search algorithm, we could construct situations in which, although
     there was a path to the ball, the robot would never be able to find it.

\paragraph{Finding the Ball:}

     The robot often loses sight of the ball while it is trying to
     manipulate it. This is usually because it has walked past the ball. It
     must search for the ball, but because it has just lost sight of the
     ball, more information is available for it to use.

     One way of solving this problem is to incorporate a full-scale world
     view into the robot architecture. Such a model would remember at what
     point the ball was last seen and attempt to steer the robot back toward
     that point. However, this would require a significant amount of
     overhead and would rely heavily on localization information in order to
     accurately move the robot.

     Instead, we implemented a very simple but extremely effective
     algorithm. When the robot loses the ball, it walks backwards for nearly
     half the width of the field. If it still does not see the ball, it
     begins the random search procedure by turning in the direction in which
     it last saw the ball. After this, the random search procedure continues
     normally.

     This two-step process almost always succeeds in finding a ball which
     the robot has briefly lost. Almost every time the robot loses sight of
     the ball, it has walked past it, or nudged it to the side. When the
     robot backs up, the ball quickly comes back into view. If it does not,
     it is likely because another robot has taken the ball away, or is
     obstructing the ball from view.

\section{Acting with Little Information}
\label{sec:lost}

     Frequently during games, the robot's localization information is so
     poor as to be useless. As explained in Section~\ref{sec:control}, the
     robot should not stop and look every time its localization information
     is bad. Therefore, we must make sure that it can act reasonably even
     when its localization information is not good enough to use.

     We have already determined in Section~\ref{sec:control} that when the
     robot does not have the ball, localization information is
     unnecessary. We will now examine the case in which the robot has
     possession of the ball.

     Our algorithm to score goals without localization information is:
\begin{enumerate}
\item Until see the goal, walk sideways to the right around the ball;
\item When see the goal, stop walking sideways;
\item Walk forward into the ball.
\end{enumerate}
     This allows the robot to consistently score goals with no localization
     information at all. However, this takes the robot much longer than it
     does when the robot has localization information.

     The difference in times is due not so much to the time the robot spends
     circling the ball (perhaps not in the most efficient direction), but
     rather to the fact that the robot spends more time moving around the
     ball. Because its movements are so error-prone, this makes it much more
     likely to tap the ball away. It then needs to look for the ball again,
     move towards it, and begin circling from the beginning.

     Although the robot is not able to walk sideways very quickly, we still
     chose to have it walk sideways around the ball instead of walking
     forward and turning frequently. The main reason for this is that the
     robot is unable to walk forward around the ball and continue to see the
     ball. Because the walking is error-prone, if the robot does not stop to
     look at the ball frequently, if quickly wanders far from its intended
     path. Not only that, but if it is not looking at the ball, it is not
     able to respond quickly to movements of the ball. However, if it stops
     to look often, it spends so much time turning towards the ball and then
     turning back to walk tangent to it that this activity dominates the
     time it spends circling the ball and it takes longer for the robot to
     round the ball than if it had been walking sideways.

\section{Upgrading Performance}
\label{sec:upgrade}

     Not only must the robot be able to progress towards its goals when it
     does not have useful localization information, but it must be able to
     improve its performance as soon as it gets such information. We used
     several different strategies to make sure that the robot's performance
     would be able to improve quickly as well as degrade gracefully as the
     availability of good information changed.

\subsection{Localization-Dependent Performance Enhancements}

     We developed three performance enhancements that rely on accurate
     localization information.

\paragraph{Circling the Ball:}

     The first helps to decide which direction to circle around the ball, or
     whether to circle. If the robot knows approximately where it is and
     approximately which direction it is facing, then it can choose the
     shortest direction to circle around the ball. With more information
     about where it is, the robot can choose not to circle into a wall, but
     to go around the other side of the ball. With enough information, the
     robot can realize that it is close to a wall and will not be able to
     get behind the ball, so should push it down the side of the field and
     wait until the corner to try to turn the ball towards the goal.

\paragraph{Skew:}

     The second enhancement helps the robot get into position behind the
     ball more efficiently. If the robot knows its orientation, then it is
     able to ``skew'' its approach to the ball. This allows it to complete
     part of the work of circling of the ball without circling and without
     localizing during the approach.

\paragraph{Scoring without Vision:}

     The third enhancement is very small, but makes a big difference. We
     specified in Section~\ref{sec:lost} that, in the absence of useful
     localization information, the robot should circle the ball until it
     sees the goal. This simply adds that it can also stop circling and
     begin to push the ball if it knows it is facing in close to the right
     direction. This enables the robot to score goals consistently even when
     it cannot see the goal at all.

\subsection{Mode-Based Architecture}

     We built a control architecture based on basic modes of behavior we
     identified as important. Knowledge about basic features of the robot's
     state, such as whether it is paused, into which goal it is trying to
     push the ball, whether it is in possession of the ball, whether it is
     close to the ball, and whether it knows where the goal is. Performance
     enhancements include switching to a different mode (for example, if the
     robot has good enough localization information, it knows where the goal
     is without seeing it, so it can appropriately change mode), and
     improving the performance of the robot within a mode.

     The modes we have defined for the attacker are:

\begin{enumerate}
\item \label{hsearching} Head Searching: the robot is searching for the ball by turning its head;
\item \label{searching} Searching: the robot is searching for the ball by turning its head and its body;
\item \label{approaching} Approaching: the robot is approaching the ball;
\item \label{circlingr} Circling Right: the robot is circling the ball to the right;
\item \label{circlingl} Circling Left: the robot is circling the ball to the left;
\item \label{yscoring} Scoring into the Yellow Goal: the robot is pushing the ball towards the yellow goal;
\item \label{bscoring} Scoring into the Blue Goal: the robot is pushing the ball towards the blue goal.
\end{enumerate}

     The algorithm we use to switch among these modes is approximately as
     follows:

\begin{enumerate}
\item If robot sees ball and is not close to it, mode = Approaching;
\item If robot does not see ball, but did recently, mode = Head Searching;
\item If robot does not see ball, and has not recently, mode = Searching;
\item If robot does not know where goal is and is close to ball, mode = {Circling Right, Circling Left};
\item If robot knows where goal is and is close to ball, mode = {Scoring into the Yellow Goal, Scoring into the Blue Goal}.
\end{enumerate}

     The decision to circle right or left depends on whether the robot knows
     where the goal is. If it does, it circles in the most efficient
     direction. If it does not, it circles to the right by default. The
     decision to try to score into the yellow or blue goal depends on a
     variable set before the program is compiled, which tells the robot
     which is its target.

     By separating the high-level behavior from its optimizable low-level
     implementation, we ensure that the robot's high-level behaviors do not
     change frequently as the available information changes. Instead, the
     way the robot executes these behaviors changes in response to the lack
     or availability of localization information.

\section{Special Cases--Urgent Action}
\label{sec:urgent}

     In some cases, the ``balance'' discussed in the previous sections of
     the paper does not apply. In these cases, immediate action is
     necessary, so the cost of localizing thoroughly is prohibitively
     high. We have found shortcuts and compromises that allow the robot to
     perform as well as possible in these special cases, even without
     spending time looking around for landmarks.

\subsection{Approaching the Ball}

     Possession of the ball is a critical part of a soccer game. The team
     that is able more frequently to possess the ball has an incredible
     advantage over its opponents. Therefore, in our strategy, when the
     robot sees the ball, it rushes towards it, not waiting to localize.

     This strategy has negatives, clearly. If the robot does not know where
     it is on the field, it will not know what to do with the ball when it
     gets to it. Nevertheless, it is better for a robot to look around when
     it is in possession of the ball than when it is farther from the
     ball. When the robot is standing near the ball, it is blocking one side
     of the ball from visibility and attacks, and is more able to respond
     quickly to an attack because it is already close by.

     Also, as discussed in Section~\ref{sec:upgrade}, even if the robot had
     only limited localization information, it could still skew its approach
     to the ball, and choose the most efficient direction when circling the
     ball.

\subsection{Kickoff}

     We were surprised to discover, in the initial games of
     \mbox{RoboCup-99}, how much an advantage is gained by winning the
     kickoff. When the ball moves to one side of the field, it is very
     difficult for the robots to move it to the other side of the field. In
     the \mbox{RoboCup-99} games, the team that won the kickoff usually won
     the point, simply because the ball never emerged from the side of the
     field to which it was initially pushed.

     Because of this, we felt it was crucial to have an extremely aggressive
     kickoff. We took advantage of the fact that, at each kickoff, the
     robots were facing the opposite goal by having them run straight
     towards the ball, which is placed in the center of the field, between
     them and the goal.

     We found it was best to allow them to run with the ball without
     localizing at all for almost half the length of the field--nearly the
     whole distance between their starting positions and the goal. Even when
     the error-prone motion of the robots causes them to stray far from
     their projected path towards the goal, they are usually able to drive
     the ball onto the other robots' side of the field before stopping to
     localize.

     This was a very important advantage in almost all of our games, since
     we were able to win most of the kickoffs. In the one game we lost, we
     had accidentally turned this feature off during the first half of the
     game, and our robots were no longer able to win the majority of the
     kickoffs. When we turned it back on in the second half, our robots
     again dominated the kickoffs, and were therefore able to score goals
     and prevent the other team's robots from scoring any.

\subsection{Goalie}

     Another time when swift action is crucial is when a robot is playing
     the position of goaltender. However, this position also requires very
     accurate localization. We went through several different algorithms for
     the goal tender before settling on one that seemed to work much better
     than the others.

     We had a lot of trouble building an effective goalie. Because it is so
     necessary for the goalie to be in the correct position in front of the
     goal, our initial algorithms all rely heavily on the localization
     module. Because of this, the robots spend a lot of time looking for
     landmarks instead of looking at the field, and so miss many
     goals.

     Also, it seems that the localization algorithm doesn't provide
     sufficiently accurate information for the goaltender position. It often
     allows the goalies to be close to the appropriate position, but not
     quite there, and so to leave large segments of the goal unblocked and
     unguarded. Not only that, but sometimes the localization information is
     wrong, and the goalies wander out across the field before discovering
     that they are in the wrong place and trying to return.

     Finally, by avoiding the localization module altogether, we were able
     to find a way for the goaltender not only to avoid looking frequently
     at landmarks, but also to position itself more accurately in front of
     the goal. Our final algorithm is as follows:

\begin{enumerate}
\item Stand, centered, in front of the goal, facing the other side of the field;
\item Scan the horizon for the ball;
\item If the ball is seen, run straight after it;
\item If lose sight of the ball for more than 2 frames, turn until own goal is seen;
\item If see own goal, run towards it until it fills visual field;
\item If own goal fills visual field, turn until opposing goal is seen.
\end{enumerate}

     This final version of the goalie is extremely aggressive, and extremely
     successful. It was used in our final game, which we won, and only one
     goal was scored against it. This happened because the robot does not
     have a full $\ang{180}$ visual field. An opponent robot was able to
     keep the ball out of the goalie's visual field by driving it along the
     side of the field and behind the goalie. We can think of few ways to
     fix it. One involves the goalie turning from side to side while
     standing in front of the goal. This has its own weakness, however,
     which is that the goalie would tend to drift away from the goal and
     would have to recenter itself periodically.

     One of the main strengths of this algorithm is that it takes advantage
     of the special situation in which the goal tender finds
     itself--standing very close to one goal, and facing the other. Because
     the goals are the largest visual features on the field, it is easy to
     use them to localize this special position. Because the goalie pushes
     the ball far away from the goal, it usually has plenty of time to run
     back to the goal and turn around before the ball comes nearby.

     This goaltender surprised us twice during the game. At one point, it
     had lost the ball and had turned around to return to the goal. But
     another robot had moved the ball so that it was right on the goalie's
     path back into position. We were sure it would push the ball into the
     goal. But because we had programmed it to walk to the largest area of
     open goal, it stepped around the ball, turned to face the field, saw
     the ball nearby, and pushed it away from the goal. This, to us, made
     our goalie the most effective one playing.

     But it had one more surprise in store for us. We purposely made the
     goaltender stop chasing the ball if it lost sight of it even briefly,
     because we did not want it to stay away from the goal for very long
     when it did not have possession of the ball. This worked quite
     well--the goalie did not have trouble clearing the ball because of
     briefly losing sight of it. In fact, during the game, our goaltender
     once managed to push the ball all the way across the field, and into
     the opposing goal!

\section{Results}
\label{sec:results}

     We ran two experiments to determine the best values for the
     localization constraints discussed in Section~\ref{sec:control}. We
     tested how long it would take one robot on an open field to score a
     goal. If the robot took longer than fifteen minutes to score a goal, we
     stopped the trial and recorded its time as fifteen minutes.

     We positioned the robot at the point (700, 450), or three-quarters of
     the way down the field from the yellow goal, and 1/4 of the way from
     the right side wall (if facing the yellow goal). We oriented the robot
     at $\ang{-135}$, or $\ang{45}$ to the left of facing straight towards
     the yellow goal. We placed the ball directly in front of it, at the
     midpoint of the width of the field, since we did not wish to time the
     robot's search algorithm. We timed how many minutes it took the robot
     to push the ball into the yellow goal.

     In Figures~\ref{fig:btw} and~\ref{fig:err}, the mean of each set
     of trials is indicated as a bold tick. Each trial is represented by a
     small tick. The grey bar around the mean is one standard deviation.

     The experiments have a very high variance because of the randomness
     inherent in the design of the robots. Not only do the results from the
     robot's sensors have non-neglible variance, but the motion of the robot
     is unreliable. Also, the localization is based on a sampling algorithm,
     and so, even with exactly the same inputs, it will often give different
     results. We believe that most of the variance is due to the high rate
     of error in the robot's motion. This unreliability is magnified when
     the ball is involved. When the robot tries to push the ball forward, it
     often ends up pushing it at an angle, or out to the side, or even
     walking past the ball. When it walks around the ball, it often
     accidentally taps it, sending the ball off in an unpredictable
     direction, as described in Section~\ref{sec:lost}.

\subsection{Enforcing Action}

\begin{figure}[htbp]
  \begin{center}
    \epsfig{file=picture1.eps,width=1.0\columnwidth}
    \caption{
      %
      Time taken to score a goal versus how long we require the
      robot to act before looking for landmarks.
      %
      }
    \label{fig:btw}
  \end{center}
\end{figure}

     The first variable we tested was how long we should force the robot to
     act before looking for landmarks. Figure~\ref{fig:btw} shows the
     results of ten trials each of three different time intervals. When the
     interval is raised to 500 frames, the robot occasionally scores
     own-goals. Because of this, we did not consider that interal a
     possibility, and did not include it in the graph.

     The standard deviations of the trials are, as shown, very
     high. Nevertheless, there is a clear penalty for localizing too
     frequently. This is because so much stopping to look disrupts the
     robot's activity. It loses sight of the ball more frequently, and must
     stop to look for it. Also, scanning the landmarks so often simply takes
     a lot of time.

     There is also a clear penalty for not localizing enough, as we found
     when we tested the 500-frame interval. If the robot does not look
     around enough, it takes it much longer to score goals. And, as
     mentioned in Section~\ref{sec:lost}, the more time the robot spends
     moving around near the ball, the more likely it is to tap the ball in
     the wrong direction, which sometimes leads it to score own-goals.

     Although our results show that 350- and 200-frame intervals are
     equivalently good, we chose to use a 350-frame interval. In an actual
     game, the penalty for stopping more often is much higher than when
     there is only one robot on the field. When a robot stops to look for
     landmarks, other robots have a chance to take the ball away.

\subsection{Less Accurate Localization}

\begin{figure}[htbp]
  \begin{center}
    \epsfig{file=picture2.eps,width=1.0\columnwidth}
    \caption{
      %
      Time taken to score a goal versus how low we require the standard deviations of the localization values for $\theta$ (the robot's orientation) and x and y (its location on the field) to be before using them.
      %
      }
    \label{fig:err}
  \end{center}
\end{figure}

     We also tested how low we should require the standard deviations of the
     localization values to be before using them. Figure~\ref{fig:err} shows
     the results of ten trials each of two different sets of standard
     deviation maxima. We also tried setting the standard deviation maxima
     lower ($\theta$ standard deviation of 5, x and y standard deviation of
     150), and higher ($\theta$ standard deviation of 60, x and y standard
     deviation of 1200), but found that with either of these settings, the
     robot frequently made own-goals. We concluded that they were unsuitable
     and excluded them from the graph.

     If we demand the localization values be too accurate before using them,
     we lose the benefit of using them frequently, and must revert to our
     original strategy, detailed in Section~\ref{sec:lost}. If we are still
     able to use them sometimes, this simply slows us down, as seen in
     Figure~\ref{fig:err}, setup A. But as mentioned in
     Section~\ref{sec:lost}, if we must rely too heavily on this strategy,
     the robot is much more likely to tip the ball in the wrong direction
     and accidentally make an own-goal. This is borne out by our experience
     with setting the maximum standard deviation values too low.

     But also, if we demand too little accuracy from the localization
     values, the robot will rely on them even when they are faulty. This is
     clearly borne out by our experience with setting the standard deviation
     values too high. The robot mistakenly believed that it knew where it
     was and pushed the ball right into its own goal.

     We chose to use the standard deviation values used in setup B from
     Figure~\ref{fig:err} ($\theta$ standard deviation of $\ang{30}$, x and
     y standard deviation of 600), because, in our experiments, there was a
     clear advantage to these settings.

     These experiments show that, although it is crucial to have a rough
     estimate of angle, it is not important for the robot to know where it
     is on the field.

\section{Conclusion}
\label{sec:conclusion}

     In this paper, we reported on our work on the control system of
     soccer-playing Sony quadruped legged robots. We briefly described the
     components of the robots and the setup of the game. We then presented
     our algorithms to control the amount of localization information the
     robot has; to score goals without that information; to employ as much
     of that information as is available and to upgrade and degrade
     performance gracefully as availability changes; and to deal with
     special cases in which more urgent action is necessary. Finally, we
     presented the results of tests we ran to determine the best way to
     control the amount of localization information the robot has.

     Results from our matches in Stockholm show our algorithms to be
     effective. Our team won all but one of its games, and the one it lost
     was lost by only one point. Our team was the only one in this year's
     league to score goals against opposing teams and never to score a point
     against itself. Our goaltender was the only one in this year's league
     to score a goal.

\section*{Acknowledgements}

     We would like to thank Sony for providing us with wonderful robots and
     walking movements to work with.  We would like to thank Jim Bruce for
     developing the vision system and Scott Lenser for developing the
     localization algorithm for our robots.  Thanks to Tucker Balch for
     helpful discussions and suggestions on this work.

     This research is sponsored in part by the Defense Advanced Research
     Projects Agency (DARPA) and the Air Force Research Laboratory (AFRL)
     under agreement numbers F30602-97-2-0250 and F30602-98-2-0135.  The
     views and conclusions contained in this document are those of the
     authors and should not be interpreted as necessarily representing
     official policies or endorsements, either expressed or implied, of the
     Air Force or the United States Government.


\bibliographystyle{plain}
\bibliography{sony}

\end{document}
