AIspace is a set of tools used to learn and teach fundamental AI algorithms. The original version of AIspace was written in Java. There was not a clean separation of the algorithms and visualization; it was too complicated for students to modify the underlying algorithms. Its next generation, AIspace2, is built on AIPython, open source Python code that is designed to be as close as possible to pseudocode. AISpace2, visualized in JupyterLab, keeps the simple Python code, and uses hooks in AIPython to allow visualization of the algorithms. This allows students to see and modify the high-level algorithms in Python, and to visualize the output in a graphical form, aiming to better help them to build confidence and comfort in AI concepts and algorithms. So far we have tools for search, constraint satisfaction problems (CSP), planning and Bayesian network. In this paper we outline the tools and give some evaluations based on user feedback.

This paper presents a meta-review of digital technology applications for dynamic environmental management, which provide contemporaneous signals and incentives to influence resource users' behaviours, thereby generating more spatially and temporally flexible responses to variable ecosystem conditions.

POMDP (Partially Observable Markov Decision Process) is a mathematical framework that models planning under uncertainty. Solving a POMDP is an intractable problem and even the state of the art POMDP solvers are too computationally expensive for large domains. This is a major bottleneck. In this paper, we propose a new heuristic, called the pairwise heuristic, that can be used in a one-step greedy strategy to find a near optimal solution for POMDP problems very quickly. This approach is a good candidate for large problems where real-time solution is a necessity but exact optimality of the solution is not vital. The pairwise heuristic uses the optimal solutions for pairs of states. For each pair of states in the POMDP, we find the optimal sequence of actions to resolve the uncertainty and to maximize the reward, given that the agent is uncertain about which state of the pair it is in. Then we use these sequences as a heuristic and find the optimal action in each step of the greedy strategy using this heuristic. We have tested our method on the available large classical test benchmarks in various domains. The resulting total reward is close to, if not greater than, the total reward obtained by other state of the art POMDP solvers, while the time required to find the solution is always much less.

We propose a novel method for solving the localization problem, particularly useful in self-similar environments. Localization is the task of determining a robot's position with little or no prior knowledge about its initial location. We introduce a computationally efficient active strategy for the localization task. The proposed method also automatically generates optimal macro actions giving the robot the ability to localize in all environments. Combining the active strategy and macro actions, the method introduces an efficient strategy for determining a robot's position in any environment where localization is possible.

This Dynamo project overview briefly describes the development of the world's first autonomous robot soccer players. The accompanying video shows the outcomes of a series of experiments using small scale radio-controlled trucks and cars to play robot soccer. These pioneering experiments in embodied intelligence were successfully carried out over the period 1992-1994 in the Dynamo project at the UBC Laboratory for Computational Intelligence. They served as precursors to the RoboCup robot soccer competitions that started in 1997.

Many older adults with cognitive impairment are excluded from powered wheelchair use because of safety concerns. This leads to reduced mobility, and in turn, higher dependence on caregivers. In this paper, we describe an intelligent wheelchair that uses computer vision and machine learning methods to provide adaptive navigation assistance to users with cognitive impairment. We demonstrate the performance of the system in a user study with the target population. We show that the collision avoidance module of the system successfully decreases the number of collisions for all participants. We also show that the wayfinding module assists users with memory and vision impairments. We share feedback from the users on various aspects of the intelligent wheelchair system. In addition, we provide our own observations and insights on the target population and their use of intelligent wheelchairs. Finally, we suggest directions for future work.

We address the problem of multi-robot area coverage and present a new approach in the case where the map of the area and its static obstacles are known and the robots have a limited visibility range. The proposed method starts by locating a set of static guards on the map of the target area and then builds a graph called Reduced-CDT, a new environment representation method based on theConstrained Delaunay Triangulation(CDT).Multi-Prim'sis used to decompose the graph into a forest ofpartial spanning trees(PSTs). Each PST is then modified through a mechanism calledConstrained Spanning Tour(CST) to build a cycle which is then assigned to an individual robot. Subsequently, robots start navigating the cycles and consequently cover the whole area. We show that the proposed approach is complete and robust with respect to robot failure.

Interactive algorithm visualizations (AVs) are powerful tools for teaching and learning concepts that are difficult to describe with static media alone. However, while countless AVs exist, their widespread adoption by the academic community has not occurred due to usability problems and mixed results of pedagogical effectiveness reported in the AV and education literature. This paper presents our experiences designing and evaluating CIspace, a set of interactive AVs for demonstrating fundamental Artificial Intelligence algorithms. In particular, we first review related work on AVs and theories of learning. Then, from this literature, we extract and compile a taxonomy of goals for designing interactive AVs that address key pedagogical and usability limitations of existing AVs. We advocate that differentiating between goals and design features that implement these goals will help designers of AVs make more informed choices, especially considering the abundance of often conflicting and inconsistent design recommendations in the AV literature. We also describe and present the results of a range of evaluations that we have conducted on CIspace that include semi-formal usability studies, usability surveys from actual students using CIspace as a course resource, and formal user studies designed to assess the pedagogical effectiveness of CIspace in terms of both knowledge gain and user preference. Our main results show that (i) studying with our interactive AVs is at least as effective at increasing student knowledge as studying with carefully designed paper-based materials; (ii) students like using our interactive AVs more than studying with the paper-based materials; (iii) students use both our interactive AVs and paper-based materials in practice although they are divided when forced to choose between them; (iv) students find our interactive AVs generally easy to use and useful. From these results, we conclude that while interactive AVs may not be universally preferred by students, it is beneficial to offer a variety of learning media to students to accommodate individual learning preferences. We hope that our experiences will be informative for other developers of interactive AVs, and encourage educators to exploit these potentially powerful resources in classrooms and other learning environments.

This paper describes the design of the CIspace interactive visualization tools for teaching and learning Artificial Intelligence. Our approach to design is to iterate through three phases: identifying pedagogical and usability goals for supporting both educators and students, designing to achieve these goals, and then evaluating our system. We believe identifying these goals is essential in confronting the usability deficiencies and mixed results about the pedagogical effectiveness of interactive visualizations reported in the Education literature. The CIspace tools have been used and positively received in undergraduate and graduate classrooms at the University of British Columbia and internationally. We hope that our experiences can inform other developers of interactive visualizations and encourage their use in classrooms and other learning environments.

The constraint-based agent (CBA) framework with prioritized constraints is a simple and effective methodology for designing and building situated robots. This methodology can be seen as a formal development of the subsumption approach. It prevents ad hoc layering of behaviors and supports modular development of the system. A situated robot called Ainia that repeatedly finds, tracks, chases, and kicks a ball is presented as an illustrative case study of this design methodology. Ainia is first modeled, simulated, and animated with the constraint nets in Java (CNJ) tool. Then, a prioritized constraint-based controller of the simulated Ainia is used to control the physical robot in the real world. The results show that the behaviors of the physical robot satisfy the requirements specification. Hence, this study provides evidence that the formal CBA framework with prioritized constraints is an effective approach for synthesizing situated robot controllers. In addition, it supports the claim that CNJ is an effective tool for designing and building situated robots operating in the real world.

UNLABELLED: We recently demonstrated that combining the output from Genscan and HMMgene can provide increased accuracy of gene predictions. We have created a robust software system that runs algorithms previously described on DNA sequences and provides a public web interface to the system for use by the biological community worldwide. The GeneComber system performs ab initio gene prediction by first taking a user inputted DNA sequence and running Genscan and HMMgene. The outputs of Genscan and HMMgene are then integrated using the EUI, GI and EUI_frame algorithms. All results are then stored into a relational database management system (RDBMS) and can then be retrieved through a web interface. The web interface provides a unified view of the GeneComber predictions by graphically overlaying outputs from Genscan, HMMgene, EUI, GI and EUI_frame. Outputs can also be retrieved in general feature format (GFF) or FASTA format. The software is written in the Perl programming language and is both dependent on and interoperable with the Bioperl toolkit. It includes high-level application programming interfaces (APIs) to run Genscan, HMMgene and a database API to insert prediction results into an RDBMS. The APIs are assembled into the genecomber script which is executed by the web interface or can be run directly from the Unix command line. The web interface is written in PHP and is structured so as to be easily modified for viewing data from any database that stores gene structures. AVAILABILITY: The GeneComber public web interface and supplementary information is located at http://bioinformatics.ubc.ca/genecomber The source code is released under the GNU General Public License and is available at ftp://ftp.bioinformatics.ubc.ca/pub/genecomber/software.

MOTIVATION: Despite constant improvements in prediction accuracy, gene-finding programs are still unable to provide automatic gene discovery with desired correctness. The current programs can identify up to 75% of exons correctly and less than 50% of predicted gene structures correspond to actual genes. New approaches to computational gene-finding are clearly needed. RESULTS: In this paper we have explored the benefits of combining predictions from already existing gene prediction programs. We have introduced three novel methods for combining predictions from programs Genscan and HMMgene. The methods primarily aim to improve exon level accuracy of gene-finding by identifying more probable exon boundaries and by eliminating false positive exon predictions. This approach results in improved accuracy at both the nucleotide and exon level, especially the latter, where the average improvement on the newly assembled dataset is 7.9% compared to the best result obtained by Genscan and HMMgene. When tested on a long genomic multi-gene sequence, our method that maintains reading frame consistency improved nucleotide level specificity by 21.0% and exon level specificity by 32.5% compared to the best result obtained by either of the two programs individually. AVAILABILITY: The scripts implementing our methods are available from http://www.cs.ubc.ca/labs/beta/genefinding/

Soccer meets the requirements of the situated agent approach and as a task domain is sufficiently rich to support research integrating many branches of robotics and AI. A robot is an integrated system, with a controller embedded in its plant. A robotic system is the coupling of a robot to its environment. Robotic systems are, in general, hybrid dynamic systems, consisting of continuous, discrete and event-driven components. Constraint nets provide a semantic model for modeling hybrid dynamic systems. Controllers are embedded constraint solvers that solve constraints in real-time. A controller for our new softbot soccer team, UBC Dynamo98, has been modeled in constraint nets, and implemented in Java, using the Java Beans architecture. The paper demonstrates that the formal constraint net approach is a practical tool for designing and implementing controllers for robots in multi-agent real-time environments.

Rigorous analysis and evaluation of real implemented robotic systems for intelligent tasks are rarely performed. Such systems are often extremely complicated, depending not only on 'interesting' theoretical parameters and models, but on many assumptions and constants which may be set almost arbitrarily. We view all task implementations as particular parameterizations of the task goals they represent. Through fractional factorial experiments we establish the statistically significant parameters and parameter interactions for a 'sensorless' model-based push-orienting task. This type of analysis is a necessary step to understanding integrated intelligent systems. It reveals aspects of system implementations which cannot easily be predicted in advance, and gives a clear picture of the task requirements, given the strengths and weaknesses of the observed system.

Knowledge-based vision for robots needs a radically new approach. The traditional approach has not made substantial progress for various reasons including the engineering problems of building systems based on a hybrid on-line/off-line paradigm. A new situated agent approach is presented. The constraint net model of Y. Zhang and A.K. Mackworth allows the designer to specify the robot's vision, control and motor systems uniformly as on-line systems. If the perceptual and control systems are designed as constraint-satisfying devices then the total robotic system, consisting of the robot symmetrically coupled to the environment, can be proven correct. Examples of this approach are given.

A shape representation technique suitable for tasks that call for recognition of a noisy curve of arbitrary shape at an arbitrary scale or orientation is presented. The method rests on the describing a curve at varying levels of detail using features that are invariant with respect to transformations that do not change the shape of the curve. Three different ways of computing the representation are described. They result in three different representations: the curvature scale space image, the renormalized curvature scale space image, and the resampled curvature scale space image. The process of describing a curve at increasing levels of abstraction is referred to as the evolution or arc length evolution of that curve. Several evolution and arc length evolution properties of planar curves are discussed.>

The curvature scale-space image of a planar curve is computed by convolving a path-based parametric representation of the curve with a Gaussian function of variance sigma /sup 2/, extracting the zeros of curvature of the convolved curves and combining them in a scale space representation of the curve. For any given curve Gamma , the process of generating the ordered sequence of curves ( Gamma /sub sigma / mod sigma >or=0) is the evolution of Gamma . It is shown that the normalized arc length parameter of a curve is, in general, not the normalized arch length parameter of a convolved version of that curve. A novel method of computing the curvature scale space image reparametrizes each convolved curve by its normalized arc length parameter. Zeros of curvature are then expressed in that new parametrization. The result is the renormalized curvature scale-space image and is more suitable for matching curves similar in shape. Scaling properties of planar curves and the curvature scale space image are also investigated. It is shown that no new curvature zero-crossings are created at the higher scales of the curvature scale space image of a planar curve in C/sub 1/ if the curve remains in C/sub 1/ during evolution. Several results are presented on the preservation of various properties of planar curves under the evolution process.>

Schema-based representations for visual knowledge are integrated with constraint satisfaction techniques. This integration is discussed in a progression of three sketch map interpretation programs: Mapsee-1, Mapsee-2, and Mapsee-3. The programs are evaluated by the criteria of descriptive and procedural adequacy. The evaluation indicates that a schema-based representation used in combination with a hierarchical arc-consistency algorithm constitutes a modular, efficient, and effective approach to the structured representation of visual knowledge. The schemata used in this representation are embedded in composition and specialization hierarchies. Specialization hierarchies are further expanded into discrimination graphs.>

The problem of finding a description, at varying levels of detail, for planar curves and matching two such descriptions is posed and solved in this paper. A number of necessary criteria are imposed on any candidate solution method. Path-based Gaussian smoothing techniques are applied to the curve to find zeros of curvature at varying levels of detail. The result is the ``generalized scale space'' image of a planar curve which is invariant under rotation, uniform scaling and translation of the curve. These properties make the scale space image suitable for matching. The matching algorithm is a modification of the uniform cost algorithm and finds the lowest cost match of contours in the scale space images. It is argued that this is preferable to matching in a so-called stable scale of the curve because no such scale may exist for a given curve. This technique is applied to register a Landsat satellite image of the Strait of Georgia, B.C. (manually corrected for skew) to a map containing the shorelines of an overlapping area.