Jacky Baltes' Publications

In 2004, the playing field size of the small sized league was significantly increased, which poses new challenges for all teams. This paper describes extensions to our current video server software Doraemon to deal with these new challenges. It shows that a camera with a side view is a workable alternative to the more expensive approach of using multiple cameras. To illustrate this point, the paper discusses the camera calibration method used in Doraemon as well as an investigation into some common two dimensional interpolation methods (pulse, linear, and cubic B-spline) as well a novel average gradient method. It also proves that (ignoring occluded parts of the playing field) it is possible to construct a realistic top down view of the playing field with a camera that only has a side view of the field.

The goal of this research is to develop an intuitive, adaptive, and flexible architecture for intelligent mobile robots. We propose a hybrid architecture that uses behaviour trees and finite state machines. A task manager selects behaviours based on approximations of their applicability and the expected reward of a behaviour. One major feature of this architecture is that important information of the perception, reasoning, and execution parts of the system are made explicit. This information includes parameters (e.g., colour definitions), structural information (e.g., the behaviour tree), and the ability to represent prototypical scenarios.

This paper describes methods used in stabilizing the walking gait of Tao-Pie-Pie, a small humanoid robot given rate feedback from two RC gyroscopes. Tao-Pie-Pie is a fully autonomous small humanoid robot (30cm tall). Although Tao-Pie-Pie uses a minimal set of actuators and sensors, it has proven itself in international competitions, winning honors at the RoboCup and HuroSot competitions in 2002 and 2003. The feedback control law is based solely on the rate information from two RC gyroscopes. This alleviates drift problems introduced by integrating the RC gyroscope feedback in the more common position control approaches.

This paper describes the methodology that we used to design and implement balancing and walking gaits for Tao-Pie-Pie, a small 30cm tall humanoid robot. Tao-Pie-Pie is a fully autonomous robot with all power, sensing, and processing done on-board. It is also a minimalistic design with only six degrees of freedom. Nevertheless, its performance is comparable to that of other more complex designs. The paper describes three patterns: (a) a straight walk, (b) a turn on the spot, and (c) a kicking pattern. Sensor feedback is provided by two gyroscopes that provide angular velocity in the left-right and forward-backward plane and a CMOS camera providing vision information. The feedback from the gyroscopes is not used to directly control the walking gait, because the signal is noisy and it would be computationally too expensive for the current processor hardware. Instead, coarse feedback from the gyroscopes is used to monitor the transition from one phase of the pattern to the next. This feedback is used to: (a) determine when a phase has completed successfully, and (b) when to change the endpoints of certain phases. Tao-Pie-Pie proved to be a successful design winning a number of honors at international competitions.

Using stereo vision in the field of mapping and localization is an intuitive idea, as demonstrated by the number of animals that have developed the ability. Though it seems logical to use vision, the problem is a very difficult one to solve. It requires the ability to identify objects in the field of view, and classify their relationship to the observer. A procedure for extracting and matching object data using a stereo vision system is introduced, and initial results are provided to demonstrate the potential of this system.

In domains such as robotic rescue, robots must plan paths through environments that are complex and dynamic, and in which robots have only incomplete knowledge. This will normally require both diversions from planned paths as well as significant re-planning as events in the domain unfold and new information is acquired. In terms of a representation for path planning, these requirements place significant demands on efficiency and flexibility. This paper describes a method for flexible binary space partitioning designed to serve as a basis for path planning in uncertain dynamic domains such as robotic rescue. This approach is used in the 2003 version of the a robotic rescue team. We describe the algorithm used, make comparisons to related approaches to path planning, and provide an empirical evaluation of an implementation of this approach.

This paper describes a path tracking controller for mobile robots using visual servoing. A highly efficient algorithm suitable for cheap and low power micro-processor is described. The algorithm uses a highly focused search in the image to approximate the offset and gradient of the path. These features are determined solely by a sweep through two rows of the image. An empirical evaluation shows that the algorithm is efficient and robustness. Furthermore, the empirical evaluation investigates the relationship between the average error and the look ahead distance as well as the weighting between the offset and gradient information.

This paper describes the results of an empirical evaluation comparing the performance of five different algorithms in a pursuit and evasion game. The pursuit and evasion game was played using two robots. The task of the pursuer was to catch the other robot (the evader). The algorithms tested were a random player, the optimal player, a genetic algorithm learner, a k-nearest neighbor learner, and a reinforcement learner. The k-nearest neighbor learner performed best overall, but a closer analysis of the results showed that the genetic algorithm suffered from an exploration-exploitation problem.

This paper describes fast demosaicing methods to quadruple the resolution of a CMOS camera. The resulting increase in accuracy in camera calibration and object detection is important for local vision robots, especially those that use computer vision as their only source of information about the state of the world. The paper describes two methods for demosaicing: interpolation and variance demosaicing. A comparison of three sample views is shown to demonstrate the increased resolution and the difference between the interpolation and variance demosaicing methods. Both demosaicing methods work well. Variance demosaicing performs better around edges in the image, but is computationally more expensive.

This paper describes a novel approach to detecting orientation and identity of robots using a global vision system. Instead of additional markers, the shape of the robot is used to determine an orientation using a general Hough transform. In addition the movement history as well as the command history are used to calculate the quadrant of the orientation. The identity of the robot is determined by correlating the motion of the robot with the command history. An empirical evaluation shows that the performance of the new video server is at least as good as that of a traditional approach using additional coloured markers.

The tutorial describes the initial steps in the development of a robotic platform that can be used for many experiments into AI. The system uses remote controlled cars as platforms and is thus inexpensive and easily available. A standard framegrabber and video camera are used to provide vision information to the processor. The tutorial will lesson the learning curve for people by describing efficient methods for image processing and control. This methods have been developed by the All Botz in the previous years and have proven their effectiveness in many games and demonstrations. Effectively, this will provide participants with solutions to the low level problems associated with soccer playing robots. Therefore, the participants of the tutorial will be able to build their own team in short time and to use it to test higher level AI and Soft Computing methods.

This paper describes a practical method for the camera calibration given a single image of a regular texture. This paper uses the calibration of images of skyscrapers as an example. The paper introduces two algorithms for the assignment of real world coordinates to feature points. The first algorithm selects five closely connected feature points and determines the orientation of the rectangular pattern. The second algorithm iteratively sorts the feature points and assigns real world coordinates to them. Lastly, the Tsai camera calibration algorithm is used to compute the camera parameters.

This paper describes a novel approach to detecting orientation and identity of robots using a global vision system. Instead of additional markers, the original shape of the robot is used to determine an orientation using a general Hough transform. In addition the movement history as well as the command history are used to calculate the quadrant of the orientation as well as the identity of the robot. An empirical evaluation shows that the performance of the new video server is at least as good as that of a traditional approach using additional coloured markers.

One of the reasons for organizing robotic games is that they allow researchers to evaluate their systems and approaches on a level playing field. This evaluation is important in a quickly developing field such as robotics with few real world applications. This paper investigates through a case-study how much participating at the RoboCup-99 competition has benefited a MSc. student at the University of Auckland. Although the participation was certainly stimulating, its influence on the research was indirect. The paper makes a number of suggestions that will make it easier to quantitatively evaluate research at these competitions and thus influence research more directly.

This paper describes adaptive path planning, a novel approach to path planning for car-like mobile robots. Instead of creating a new plan from scratch, whenever changes in the environment invalidate the current plan, the adaptive path planner attempts to adapt the old plan to the new situation. The paper proposes an efficient representation for path that is easily amendable to adaptation. Associated with the path planner is a set of repair strategies. These repair strategies are local methods to fix a plan to compensate for object movement in the domain. The repair strategies are specific and have a high probability of being able to fix a plan. An empirical evaluation shows that adaptive path planning is suitable to highly dynamic domains, such as . Adaptive path planning reduces the cumulative planning time by a factor of 2.7 compared to Bicchi's planner. At the same time, the quality of the plans generated by the adaptive path planner were similar to those generated by Bicchi's planner.

This paper describes a benchmark suite for mobile robots that provides quantitative measurements of a mobile robot's ability to perform specific tasks. Guidelines for the design of benchmark tests were derived from other areas faced with the problem of evaluating complex systems. The benchmarks test the control and accuracy of the path and trajectory tracking, the static path planning, and the dynamic path planning ability of a mobile robot. A set of metrics that provide important information about a mobile robot's performance are also presented. These benchmarks could also be used as simple games. Their inclusion in robotic games will lead to an increased opportunity fo researchers to evaluate their work without having to buy expensive or special purpose equipment.

This paper discusses some important features, which make the All Botz, the University of RoboCup team, a very unique team. In particular, the use of cheap hardware and the design of the video server.

This paper investigates the use of reinforcement learning in solving the path-tracking problem for car-like robots. The reinforcement learner uses a case-based function approximator, to extend the standard reinforcement learning paradigm to handle continuous states. The learned controller performs comparable to the best traditional control functions in both simulation and also in practical driving.

This paper describes a practical method for calibrating the geometry and colour information for cameras surveying large rooms. To calibrate the geometry, we use a semi-automatic system to assign real world to pixel coordinates. This information is the input to the Tsai camera calibration method. Our system uses a two stage process in which easily recognizable objects (squares) are used to sort the individual data points and to find missing objects. Fine object features (corners) are used in a second step to determine the object's real world coordinates. An empirical evaluation of the system shows that the average and maximum errors are sufficiently small for our domain. Objects are recognized through coloured spots. The colour calibration uses six thresholds (Three colour ranges (Red, Green, and Blue) and three colour differences (Red - Green, Red - Blue, Green - Blue)). This paper describes a fast threshold comparison routine.

This paper describes an architecture for path planning and control of car-like mobile robots. The method is based on a subsumption architecture with four individual behaviors: approach, steer, turn, and progress. The coordination of these simple behaviors results in a robust control architecture for mobile robots that performed well when compared to other control methods. The controller also results in simplifying the requirements on the path planner.

This paper describes the design and implementation of Ferret, an information-seeking assistant that helps a user find information on the World Wide Web. It analyzes and automatically clusters the returned pages from a search engine.

This paper describes a fuzzy logic controller for car-like mobile robots. It also introduces a simple heuristic that helps a designer in the specification of fuzzy input and output sets. The design of fuzzy rules follows intuitively from the design of the fuzzy input sets. In practical tests, this Fuzzy Logic controller resulted in greatly reduced errors and also resulted in a control law with 75% less control work than a traditional sliding mode controller.

This paper describes the design and implementation of an embedded system for the low level control of autonomous mobile robots. The micro controller board provides more accurate speed and direction control, more reliable digital communication, and facilities for additional sensors and actuators. The velocity control is implemented by a one bit D-A converter using pulse width modulation. The data rate of the digital communication is limited to five Bytes/sec., which is sufficient for simple navigation tasks.

This paper describes the design of an interface board which by emulating the bus of some popular home computers can control legacy hardware through a generic parallel port interface and serial interface. In particular, the board is currently being used to control two Mentor robot arms from a PC. We also developed firmware and a device driver for the Linux operating system.

This paper describes our practical experiences and methods for calibrating a large room. We show a semi-automatic system to assign real world coordinates to image features. Our system uses a two stage process in which easily recognizable objects (squares) are used to sort the individual data and to find missing objects. Fine object features (corners) are used in a second step to determine the image real world coordinates. An empirical evaluation of the system shows that the average and maximum errors are sufficiently small for our problem domain (autonomous mobile agents playing soccer)

This paper discusses the design of an interface for a PC and a commercially available remote-controlled car. The objective of the project is to provide the capability for a PC to emulate a conventional RC transmitter. The micro-controller-based design provides the best means of extendibility and flexibility where future requirements are yet to be defined, it also significantly reduces the processing requirements on the host PC and the client application. The data communications between the host PC and the interface is via a standard parallel port implementation that provides a platform independent communications medium. The firmware design is based on a single, restart-able task paradigm with interrupts for communications and other system functions. This is motivated by a need for quick execution of commands by the interface. An active braking application was used to evaluate advanced functionality, which produced encouraging results, and showed superior control compared with the original manual controller. A client application was written to test the functionality of the interface and data communications.

This paper introduces multi-strategy planning and describes its implementation in the system, which can combine many different planning strategies, including means-ends analysis, macro-based planning, abstraction-based planning (reduced and relaxed), and case-based planning on a single problem. Planning strategies are defined as methods to reduce the search space by exploiting some assumptions (so-called planning biases) about the problem domain. General operators are generalizations of standard operators that conveniently represent many different planning strategies. The focus of this work is to develop a representation weak enough to represent a wide variety of different strategies, but still strong enough to emulate them. The search control method applies different general operators based on a strongest first principle; planning biases that are expected to lead to small search spaces are tried first. An empirical evaluation in three domains showed that multi-strategy planning performed significantly better than the best single strategy planners in these domains.

This paper introduces multi-strategy planning, which focuses on the selection and combination of different planning methods. Planning is the problem of finding a sequence of actions (operators) that will take an agent from one state (initial state) to a desired state (goal). This problem has gotten considerable attention in artificial intelligence. Unfortunately, theoretical results show that the general planning problem is intractable in complex domains. Therefore, a practical planning system reduce the search space. This reduction of the search space is based on assumptions (so called planning biases) about the problem such as: the problem order, plan structure, or subgoal hierarchy. Given these assumptions about the task, a planning strategy exploits the reduction in the search space and searches the resulting search space. Popular examples of planning strategies are means-ends analysis, case-based planning, macro-operators, abstraction hierarchies, and non-linear planning. Planning strategies based on a specific planning bias work well in domains, in which these assumptions are satisfied, but fail if these assumptions are not met. Furthermore, in complex domains it is possible that only parts of a task can be efficiently solved with a given planning method. But for other parts of the tasks, a different planning strategy may be appropriate.

Multi-strategy planning focuses on the selection and combination of different problem solving methods. Since planning is intractable in complex domains, researchers have developed different methods to restrict, restructure, or reorder the search space and to search the new space. These reformulations of the search space are based on assumptions about the domain or other features of the task such as the problem order, plan structure, or subgoal hierarchy. These planners, then, work well in domains where the underlying assumptions are met, and fail otherwise. Furthermore, in complex domains it is possible that only parts of a task can be efficiently solved with a given planning method. But for other parts of the tasks, a different planning strategy may be appropriate. The goal of multi-strategy planning is to alleviate this problem by selecting and combining different problem solving methods on a single problem. First, planning is seen as search through the space of partial plans. Different planning strategies can be described by the language of partial plans, the set of transformations on partial plans, and the search method. Secondly, the thesis develops a theory of multi-strategy planning and shows that a multi-strategy planner can exponentially improve performance over a single strategy planner and derives sufficient conditions for this improvement. Thirdly, the thesis proposes general operators ( operators with added refinements) as a representation for different planning strategies and shows how general operators can represent different planning methods. Fourthly, the thesis develops a search control method that, given a planning method expressed as a general operator reduces the associated search space similarly to the original problem solving strategy. cheapest first method. Based on that all planning strategies have similar reduction smallest refinement generation of general operators may be cumbersome by hand, and since the system is intended as a part of a learning apprentice system, learns new general operators from examples. The planning bias learners are highly specific methods that have knowledge of 's operator set and search method and create new general operators to exploit a given planning bias. Through an empirical evaluation, this research shows (a) that multi-strategy planning improves the performance over single strategy planning in some toy domains, (b) that multi-strategy planning can solve problems in at least one complex domain (the kitchen domain), and (c) and that an unordered subproblem coordinated multi-strategy planner performs better in the kitchen domain than a problem coordinated one.

The reviewed book is intended as a practical guide to transputer hardware design. The authors do not assume prior knowledge of the transputer architecture, but the reader should be familiar with more conventional micro-processor design.

This paper describes different technologies that were used in a VLSI design course at the university of Calgary. The main goal of this paper is to show how the advent of new technology allows students to spend more time on design capture, logic simulation, and the design of test vectors, as opposed to the tedious tasks of implementing/fabricating a design and a test environment. This trend has lead to more and more complex and interesting projects. In recent years, the students used VHDL to create a behavioral description of their circuit and synthesize a schematic from it. The synthesis targets Actel or Xilinx FPGAs. The example project is the design of a GCD circuit, which the authors selected because of a number of desirable characteristics: most importantly, (a) it is complex enough to allow the students freedom in their design, and (b) it can easily be adapted to the available hardware resources. The paper includes a small example of the conversion from an algorithm into a finite state machines, one of the crucial steps in the design phase. In the future, we hope to use configurable hardware (the Algotronix ) with a powerful connection to a host computer. This will allow students even greater flexibility in their design, since they can choose which parts are implemented in hardware and which are done through software.

Our research goal is to design systems that enable humans to teach tedious, repetitive, simple tasks to a computer. We propose here a learner/problem solver architecture for such a system. The problem solving module is able to combine diverse problem solving strategies on a single problem, by using a common representation for operators, and learning operators by analyzing solution traces. At the distributed processor level, the design provides a general dynamic load balancing system that has little domain knowledge. It is controlled from the next level by a tightly constrained planner. The distributed problem solver testbed enables us to design, experiment with, and evaluate our combined learning/problem solving system for automating users' repetitive tasks.

It is well-recognized that in practical inductive learning systems the search for a concept must be heavily biased. In addition the bias must be dynamic, adapting to the current learning problem. Another important requirement is sustained learning, allowing transfer from known tasks to new ones. Previous work on dynamic bias has not explicitly addressed learning transfer, while previous case-based learning research suffers from a variety of problems. This paper presents a method of Case-Based Meta Learning (CBML), in which the cases are concepts, rather than instances, and retrieved similar concepts are used as a skeletal version space to speed up learning. CBML is independent of the concept representation language. The CBML-Clerk system, which learns repetitive operating system tasks, is presented as a demonstration.

It is well-recognized that in practical inductive learning systems the search for a concept must be heavily biased. In addition the bias must be dynamic, adapting to the current learning problem. Another important requirement is sustained learning, allowing transfer from known tasks to new ones. Previous work on dynamic bias has not explicitly addressed learning transfer, while previous case-based learning research suffers from a variety of problems. This paper presents a method of Case-Based Meta Learning (CBML), in which the cases are concepts, rather than instances, and retrieved similar concepts are used as a skeletal version space to speed up learning. CBML is independent of the concept representation language. The CBML-Clerk system, which learns repetitive operating system tasks, is presented as a demonstration.

Planning will be an essential part of future autonomous robots and integrated intelligent systems. After giving a brief introduction to the classical planning paradigm, this paper focuses on learning problem solving knowledge in planning systems. A general weak method for learning useful operators is the creation of macros. The paper first describes a novel approach to the selection and dynamic filtering of macros. The dynamic filtering approach is suggested for controlling the creation of operators. A new planning representation is proposed that uses a common representation for macros, abstractions, and cases. A general operator is represented by sequences of primitive or non-primitive operators. A macro is equivalent to a sequence of primitive, executable, operators with uninstantiated arguments. A case consists of primitive operators with instantiated arguments. An abstract plan is equivalent to a sequence of non-primitive operators at a lower level of abstraction. A learned indexing mechanism allows rapid access to relevant operators. The system is able to use both classical and case-based techniques. The general operators in a successful plan derivation would be assessed for the potential usefulness, and some stored.

The symmetric version space algorithm (SVS) learns disjunctions of string patterns by example. The learnable string concepts are a subset of regular expressions. The running time of the algorithm is reduced, because the system learns a top-down description of the string concepts. Different parts of the algorithm learn descriptions at different levels of the concept independently. This technique is similar to factoring the version space, in order to restrict the search space. The problem of fragmentation of the G-set is overcome by using a symmetric version space approach.