\documentstyle[IEEEtran]{article} \begin{document} \tolerance 10000 \title{Interval Methods in Mobile Robot Control} \author{Kung Chris Wu} \pagestyle{myheadings} \markright{APIC'95, El Paso, Extended Abstracts, A Supplement to the international journal of {\rm Reliable Computing}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \maketitle \begin{abstract} Interval methods are used in the design of a cheap and efficient mobile robot. \end{abstract} \auffil{The author is with the Department of Mechanical and Industrial Engineering, The University of Texas at El Paso, El Paso, TX 79968. This research was partially funded by the University of Texas at El Paso under the University Research Institute Grants 14-5077-6850.} \section{Formulation of a Problem} \subsection{Making a robot move is important} The majority of working robots of today are stationary. They are automating the tasks that do not require lots of moving. It would be nice to automate tasks that do include moving. How to make a moving robot? If we want a robot to perform more or less routine operations on a factory floor (e.g., move materials), then we can wire this floor and use these guiding wires to control the robot. For more complicated tasks, especially if they include moving in an unknown environment, we must equip a robot with the ability to make complicated decisions. \subsection{A cheap robot is necessary} Contemporary state-of-the-art autonomous mobile robots (AMRs) use complex calculational and reasoning schemes for autonomous navigation in alien environments (see, e.g., \cite{D88,GS87,PWSP92}). Though powerful and versatile, those AMRs are extremely costly and computationally intensive. This makes them inaccessible to many cost-sensitive industrial applications. In navigating a robot, the main computational power is used to solve the navigation problem. Crudely speaking, this problem is formulated as a mathematical optimization problem, and then solved by using methods of optimal control theory. The main idea behind intelligent control is as follows: why should we repeat these calculations ``from scratch'' every time if we can use the experience of experts who are successfully controlling the motion in an unknown environment? So, instead of solving an optimization problem, we ask the expert drivers to formulate these rules, and apply fuzzy control methodology to transform these informal rules into a precise control strategy. This idea has been successfully implemented (see, e.g., \cite{WJP93,W94,Wu 1994}). As a result, we get a small and relatively cheap autonomous robot that is almost as good in navigating as a human driver whose experience it simulates. \subsection{How our robot works} One of the main limitations of the human driver is that he can control at best one or two control parameters. Therefore, e.g., in a car, although there are many parameters that can potentially be controlled, we have to restrict their set to two: the speed (controlled by accelerator), and the angle (controlled by the steering wheel). Experienced drivers know that in difficult road conditions, it is desirable to control, e.g., each wheel separately, but there is no direct way to do that. When we make a robot, we are no more bounded by this limitation. An on-board processor can control several independent parameters at a time almost as easily as just one parameter. This makes the motion of a AMR much better. E.g., if a human driver needs to turn a car around, he is limited to steering wheel turns, so his turn requires a lot of space. AMR is not going to operate on a highway system, so this space may not always be available, in which case an AMR that simulates human driving too closely will simply get stuck. The natural way to overcome this difficulty is to have separate controllers on two wheels. It is actually sufficient to have two controllers that control two engines attached to diagonally opposite wheels. By moving these wheels straightforward, we get a straight-line motion. By moving them clock-wise, we can make this robot turn around on the spot, without wasting any space at all. This idea has been implemented in our robot \cite{W94}, and we have found out that it successfully navigates through different environments (including a specially designed complicated maze). \subsection{The problem} The algorithms that control our robot come from intelligent control (see, e.g., \cite{KL94}). They originate from the rules formulate by the experts in terms of natural language, like ``if the deviation is large, then ...''; ``if the deviation is small, then do ...'', etc. In order to formalize these rules, we must describe what ``large'', ``small'', etc., mean. If we know that, e.g., possible deviations from the desired orientation are in the interval $[-5^o,5^o]$, then we can identify deviations $\approx 5$ degrees as large, those that are $\ll 5$ as small, etc., and get a reasonable control strategy. However, we want our robot to operate successfully in {\it different} environments. Now. suppose that the environment has become smoother, so that the deviations are only from $-1^o$ to $1^o$. In this new environment, it makes no big sense to still use the rules that were designed for the entire interval $[-5,5]$. It is necessary to {\it scale down} the control, so that the basic interval will now be equal to $[-1,1]$. Vice versa, if the robot suddenly moves into a rougher terrain, we must {\it scale up} the domain of our control, because we can now encounter the values that are much larger than 5 degrees. In short: \begin{itemize} \item if we see that all the measured deviations are within a small part of the original interval, then we must choose a new, smaller interval domain; \item if we get deviations outside the original interval domain, then we must choose a new, larger interval domain. \end{itemize} The question is: {\it how to scale intervals?} \section{Main Idea} We want to design a function $f$ that transforms an interval ${\bf a}=[a^-,a^+]$ that represent the original interval domain into an interval $f({\bf a})$ that represents a new interval domain. The values $a^\pm$ are obtained from measurements. The numerical values depend on what starting point we used, and on what unit we have chosen. For example, assume that we are measuring time, and as a result we get $35\pm 5$ (i.e., a set ${\bf a}=[30,40]$). If we now change the starting point for measuring time, e.g., take $-5$ as the new starting point, then the same result will be expressed as ${\bf a}+5=40\pm 5=[35,45]$. It is natural to demand that the transformation $f$ should not depend on the choice of the starting point. This means the following: \begin{itemize} \item If we use the original starting point, then the original interval domain is described by the interval ${\bf a}=[a^-,a^+]$. If we apply the function $f$ to this domain, we get $f({\bf a})$. \item If we choose a starting point that is $a$ units before the original one, then the same original interval domain will be described by new numerical values: ${\bf a}+a=[a^-+a,a^++a]$. If we apply the same transformation to these new values, we get the interval $f({\bf a}+a)$. \end{itemize} We want these two intervals to coincide: \begin{itemize}\item the interval $f({\bf a})$ in the old units, and \item the interval $f({\bf a}+a)$ in the new units. \end{itemize} To compare these intervals, we must transform both intervals to one and the same starting point. For example, if we transform $f({\bf a})$ to new units, we will get $f({\bf a})+a$. This new interval must coincide with $f({\bf a}+a)$: $$f({\bf a}+a)=f({\bf a})+a.\eqno{(1)}$$ A similar condition can be formulated if formalize the idea that the transformation $f$ should not depend on the choice of a unit. If, instead of the original unit (e.g., sec.), we use a new unit that is $\lambda$ times smaller (e.g., millisec.), then the numerical values will increase $\lambda$ times, and instead of ${\bf a}=[a^-,a^+]$, we will have $\lambda\cdot{\bf a}=[\lambda \cdot a^-,\lambda\cdot a^+]$. In this case, a similar invariance condition can be expressed as $$f(\lambda\cdot{\bf a})=\lambda\cdot f({\bf a}).\eqno{(2)}$$ Now, we are ready for the formal definition: \section{Definition and the Main Results} \noindent{\bf Definition 1.} \begin{itemize} \item We say that a function $f$ from intervals to intervals is {\it translation-invariant} if it satisfies condition (1) for every interval $\bf a$ and for every real number $a$. \item We say that a function $f$ from intervals to intervals is {\it scale-invariant} if it satisfies condition (2) for every interval $\bf a$ and for every positive real number $\lambda>0$. \end{itemize} \noindent{\bf THEOREM.} {\it Every translation-invariant and scale-invariant function from intervals to intervals has the form $$f([a^-,a^+])=$$ $$[{a^-+a^+\over 2}+{a^+-a^-\over 2}\cdot b^-, {a^-+a^+\over 2}+{a^+-a^-\over 2}\cdot b^+]$$ for some real numbers $b^\pm$.} \smallskip \noindent{\it Comments.} \begin{itemize} \item This result was proven together with S. Starks and V. Kreinovich. \item For a different application of this result, see \cite{Starks 1994}. \item In our case, we are interested in specific intervals, namely, intervals that describe deviation. There intervals are usually symmetric with respect to 0, i.e., they have the form $[-\Delta,\Delta]$ for some $\Delta>0$. We would like the transformation intervals to be also of this type. \end{itemize} \noindent{\bf Definition 2.} \begin{itemize} \item We say that an interval ${\bf a}=[a^-,a^+]$ is {\it symmetric} if $a^-=-a^+$. \item We say that a function $f$ is {\it symmetry-preserving} if it transforms symmetric intervals into symmetric ones. \end{itemize} \noindent{\bf PROPOSITION.} {\it If $f$ is a translation-invariant, scale-invariant, and symmetry-preserving function from intervals to intervals, then there exists a real number $C>0$ such that for every symmetric interval, $f([-a,a])=[-C\cdot a,C\cdot a]$.} \smallskip \noindent{\it Comment.} So, natural invariance demands lead to a very simple rescaling: we just dilate or shrink the interval. This rescaling was experimentally compared with more complicated ones, and it turned out to perform better. In the actual implementation, we use $C=1/2$ for shrinking, and $C=2$ for expanding, because inside the processor, where all the numbers are represented in the binary form, multiplication and division by two are the easiest to implement: they are equivalent to shift by one bit. \section{Proofs of the Theorem and the Proposition} Let us denote the endpoints of the interval $f([-1,1])$ by $[b^-,b^+]$. Them, for an arbitrary $c>0$, due to scale-invariance, $$f([-c,c])=cf([-1,1])=c\cdot[b^-,b^+]=$$ $$[c\cdot b^-,c\cdot b^+].$$ In particular, if $f$ is symmetry-preserving, then $b^-=-b^+$, so we get the proof of the Proposition (with $C=b^+$). In the general case, an arbitrary interval $[a^-,a^+]$ can be represented as $m+[-c,c]$, where $m=(a^-+a^+)/2$, and $c=(a^+-a^-)/2$. Since $f$ is dilation-invariant, we conclude that $f([a^-,a^+])=m+f([-c,c])=[m+c\cdot b^-,m+c\cdot b^+]$. Q.E.D. \begin{thebibliography}{99} \bibitem{D88} M. Daily et al, ``Autonomous cross-country navigation with the ALV'', {\it Proceedings of the IEEE International Conference on Robotics and Automation}, 1988, pp. 377--389. \bibitem{GS87}Y. Goto and A. Stentz, ``The CMU system for mobile robot navigation'', {\it Proceedings of the IEEE International Conference on Robotics and Automation}, 1987, pp. 99--105. \bibitem{KL94}A. Kandel and G. Langholtz (Editors), {\bf Fuzzy Control Systems}, CRC Press, Boca Raton, FL, 1994. \bibitem{PWSP92} F. G. Pin, H. Watanabe, J. R. Simon, and R. S. Pattay, ``Autonomous navigation of a mobile robot using custom-designed qualitative reasoning VLSI chips and boards'', {\it Proceedings of the IEEE International Conference on Robotics and Automation}, 1992, pp. 123--128. \bibitem{Starks 1994} S. Starks, ``An interval approach to congestion control in computer networks'', {\it These Proceedings}, 1994. \bibitem{Wu 1994}K. Chris Wu, ``A robot must be better than a human driver: an application of fuzzy intervals''. In: L. Hall, H. Ying, R. Langari, and J. Yen (eds.), {\it NAFIPS/IFIS/NASA'94, Proceedings of the First International Joint Conference of The North American Fuzzy Information Processing Society Biannual Conference, The Industrial Fuzzy Control and Intelligent Systems Conference, and The NASA Joint Technology Workshop on Neural Networks and Fuzzy Logic, San Antonio, December 18--21, 1994}, IEEE, Piscataway, NJ, pp. 171--174. \bibitem{W94}K. C. Wu, ``Fuzzy logic control of a robot mouse'', {\it Proceedings of the 5th International Symposium on Robotics and Applied Manufacturing}, Maui, Hawaii, August 1994. \bibitem{WJP93}K. C. Wu, R. K. Joseph, and N. K. Thupili, ``Evaluation of classical and fuzzy logic controllers for wind turbine yaw control'', {\it Proceedings of the 1993 IEEE Regional Conference on Aerospace Control Systems}, Rockwell Science Center, Thousand Oaks, CA, May 25--27, 1993. \end{thebibliography} \end{document} \end{document}