Abstract:
A wheelchair navigation system for a motorized wheelchair includes dual cameras, proximity sensors, microphones, and rotation sensors for the wheels. Small markers are placed on the walls of a location or room. The navigation system uses the proximity sensors, rotation sensors and cameras in conjunction with the specialized software to determine where objects or impediments are located in the room and thereby redirect the path of the wheelchair so as to avoid such objects. The wheelchair is walked through the marked location thereby ‘teaching’ various paths which are recorded in the computer and recalled later when the wheelchair is in use. The proximity sensor perform sensing operations during performance of the teaching functions for thereby permitting avoidance of wheelchair collision with obstacles during navigation of the wheelchair through a taught trajectory and allowing for close approach of the wheelchair to solid bodies present during performance of the teaching functions.

Description:
RELATED APPLICATIONS 
   This application is a continuation-in-part of application Ser. No. 10/187,989, filed Jul. 2, 2002, now U.S. Pat. No. 6,842,692. 

   BACKGROUND OF INVENTION 
   a. Field of Invention 
   This invention relates to a wheelchair navigation system, and more particularly to a computer-controlled power wheelchair navigation system that allows a person to navigate through a location with pre-established paths, and with voice or manually activating the computer. 
   b. Description of Related Art 
   A significant population of severely disabled people require mobility assistance in daily living activities beyond what is available in conventional powered wheelchairs. The present invention is aimed at a segment of that population, those unable to manually guide the movements of powered wheelchairs, to provide them with autonomous navigation capabilities in repetitively used environments such as homes, offices, hospitals, and public buildings and spaces. 
   There are a number of navigational methods that already exist for autonomous and semi-autonomous vehicles. Current navigational systems for semi-autonomous vehicles usually have controls such as a joystick or an ocular device, and employ overriding features such as obstacle or collision avoidance. Some autonomous systems utilize path-following methods such as a magnetic strip, optical strip or targets to provide paths from an origin to a destination. These methods have difficulty handling multiple and intersecting paths, if they can handle them at all. 
   There are three systems specifically identified in the prior art, all of which differ from the present invention. A robotic wheelchair system, commonly known as the WHEELSELSY, developed by the Massachusetts Institute of Technology Artificial Intelligence Laboratory, operates as a semi-autonomous system that is capable of being controlled by head and eye movements of the rider. 
   Another wheelchair system known as NavChair® is an adaptive shared control system that is semi-autonomous. The NavChair® uses guidance command from the rider and exerts control in areas such as obstacle avoidance or object approach. 
   The Wheelchair Project also has a system that uses landmark recognition and obstacle avoidance as well as interaction across a spectrum of automations from low level motion guidance to selection of destination wherein the wheelchair delivers the rider. 
   None of these known assistance devices are fully autonomous operations. Moreover, none of these known assistance devices permit avoidance of wheelchair collision with obstacles during navigation of the wheelchair through a taught trajectory while allowing for close approach of the wheelchair to solid bodies present during performance of teaching functions. They do, however, share many common features, including adaptability to a multitude of different vehicles, varying levels of operator control authority, and obstacle avoidance. 
   The autonomous navigation system of the present invention was developed for use in rehabilitative or therapeutic environments as well as domestic and vocational circumstances. It can also be modified for use in independent mobile circumstances for the severely disabled such as public access buildings like museums and airports. Secondary applications for autonomous transport are also foreseeable, although not specifically identified herein. 
   SUMMARY OF INVENTION 
   An object of the present invention is to provide a navigation system that will enable independent mobility for handicapped people. 
   Another object of the present invention is to provide a computer-controlled wheelchair that is capable of navigating in various spaces via pre-determined paths of travel, based upon the approach disclosed in the article, “Extending Teach-Repeat to Nonholonomic Robots,” Skaar, S. B. and Yoder, J. D. 
   Yet another object of the present invention is to permit avoidance of wheelchair collision with obstacles during navigation of the wheelchair through a taught trajectory and allowing for close approach of the wheelchair to solid bodies present during performance of teaching functions. 
   The present navigation system utilizes a commercially available powered wheelchair that has been modified to include hardware, encoding devices to provide odometry, video capture devices to provide absolute position information, ultrasonic sensors to detect obstacles, as well as drive and navigation systems. The computer&#39;s software has the function of path and destination learning, recognition of obstacles, and navigation to a selected destination. 
   The computer-controlled power wheelchair of the present system is a learning, autonomous, obstruction avoiding, navigation system for motorized wheelchairs. The system learns by being driven over the desired routes to the selected destinations and committing the routes and destination to memory via the computer system. After learning the route, the wheelchair is capable of autonomously navigating any of the learned routes which is selected by the rider. The ‘teach and learn’ system of route establishment is unique within this field of application. The present system is also capable of easily and accurately maneuvering through doorways. 
   The present computer-controlled power wheelchair navigation system provides the physically disabled rider with means of ‘on command’ navigation over frequently used paths. The system was designed to operate either with guidance from the rider or with rider input consisting of a destination command (autonomous operation). This system utilizes any commercially available motorized wheelchair as its base, and is powered by three onboard batteries. A battery charger is also included to keep the batteries charged and operable. 
   Navigation within the system is carried out by use of a known filter-based estimator, such as that by Kalman®. The estimator is used in conjunction with interface software running on an onboard laptop computer. Dual cameras, proximity sensors, microphones, and rotation sensors for the wheels are all mounted to the wheelchair. These electronic components are used with the specialized software in conjunction with small visual markers placed on the walls of the location to be navigated which provide an accurate path over which the wheelchair travels. 
   The wheelchair is ‘taught’ or has pre-programmed paths to various destinations by having an able-bodied person push the chair once, with or without the rider, along any desired route of travel while the computer records information from the sensors. Once destinations have been established, the rider can then select any of these locations and the navigation system will steer the wheelchair to that location. Paths can be reversed and/or merged to reach a desired location, or in order to avoid an obstacle. The system will choose the shortest uninterrupted path to its destination. 
   The computer can be operated by two modes of operation: voice mode and switch mode. In the voice mode, the rider controls the navigation system by speaking commands into a microphone that is attached to the wheelchair and connected to the computer. If the rider cannot address the correct command, they can request a scan of all available commands. A list is simultaneously displayed on the screen and spoken by the text-to-speech converter, when the correct command is selected. 
   In switch mode, the computer reads the available locations aloud through a speech synthesizer and earphone. When the desired location is spoken, the rider triggers a switch identifying the location. Switching mechanisms have been mounted in various locations on the chair and can be activated by virtually any part of the rider&#39;s body. 
   The rider can give commands to the computer controlling the chair at any time during navigation. Such commands can be issued by speaking words or by switching triggers. Some common commands that may be used include: stop, continue travel, return to the last starting point, go faster or slower, and pause the navigation system; however such commands are not limited to these particular commands, but may be customized to fit the rider&#39;s needs. 
   When the rider chooses a destination, they will receive feedback from the computer either by a visual display or by synthesized speech. Proximity sensors located on the wheelchair locate obstacles that are in the path of the wheelchair during travel. The sensors trigger the computer to stop the wheelchair if travel is obstructed. The system does not allow the wheelchair to continue to the selected destination until the object is removed, and the wheelchair can be directed to return to a previous point so that it may travel to an alternate destination. 
   With respect to alternative navigation technologies, fixed track systems pose numerous disadvantages: difficult and inflexible implementation, undue complexity as the number of intersecting paths grows larger, and inability of the wheelchair to depart from and return to the prescribed path without outside intervention. Use of sonar for point-to-point navigation presents such problems as specular reflection (spurious measurements obtained when sonar ‘bounces’ off multiple surfaces) and the likelihood of multiple chairs intercepting each other&#39;s navigation signals in institutional settings. 
   In contrast, multiple chairs fitted with the vision-based navigation technology may readily share wall-mounted cues without difficulty, and the navigation system&#39;s use of sonar to locate obstacles within 2-3 feet of the chair is significantly less challenging than employing sonar for navigation. Finally, some researchers are investigating autonomous navigation via video detection of ‘natural landmarks’, i.e. locating and steering toward a door by identifying a doorknob. In comparison, the present navigation system relies on images with a distinctive ‘signature.’ This lends itself to significantly simpler and more straightforward implementation with negligible danger of the estimator becoming ‘confused’. Of course, the navigation system technology is inherently limited to modified environments, those defined by cue placement and taught paths. 
   Other objects, advantages and novel features of the invention will become more apparent from the following detailed description of the invention when taken in conjunction with the accompanying drawings. 
   The invention achieves the aforementioned exemplary objects by providing a wheelchair navigation system including, a motorized wheelchair, and at least one computer having software that performs navigational functions, teaching functions, obstacle detection, supervisory tasks, and diagnostic analysis. The navigation system may further include at least one camera, at least one proximity sensor, at least one rotation sensor, at least one visual sensor, at least one visual marker, and an input device including a switch or a microphone. The rotation sensor, visual sensor and the input device may be interfaced to the computer which runs specialized software, and the proximity sensor performs sensing operations during performance of the teaching functions for thereby permitting avoidance of wheelchair collision with obstacles during navigation of the wheelchair through a taught trajectory and allowing for close approach of the wheelchair to solid bodies present during performance of the teaching functions. 
   For the wheelchair navigation system described above, the computer may include a screen with a visual display, and receive information from the cameras and the sensors, process the information and determine a path of travel for the wheelchair from such information. The computer may further be voice or manually activated. 
   The invention yet further provides a wheelchair navigation system including a motorized wheelchair, at least one battery, a battery charger, a filter-based estimator with interface software, a computer having software that performs navigational functions and teaching functions, at least one camera, at least one proximity sensor, at least one microphone, at least one rotation sensor for the wheels, the at least one sensor is mounted on the wheelchair, and a plurality of visual markers capable of being placed on the walls of a specific location. The proximity sensor may perform sensing operations during performance of the teaching functions for thereby permitting avoidance of wheelchair collision with obstacles during navigation of the wheelchair through a taught trajectory and allowing for close approach of the wheelchair to solid bodies present during performance of the teaching functions. 
   The invention also provides method of navigation using a powered wheelchair including the steps of, providing a motorized wheelchair, the wheelchair being powered by at least one onboard battery, and a battery charger and having dual cameras, proximity sensors, a microphone and rotation sensors for sensing wheel rotation, providing a filter-based estimator with interface software running that is operated on at least one computer including a control system, and providing markers at various locations within a specific area. The method may further include the steps of teaching at least one path by walking the wheelchair through the at least one path prior to the wheelchair navigation system being used for independent travel, and recording the at least one path in the computer, sensing the markers with the proximity sensors and the cameras during performance of the teaching for thereby permitting avoidance of wheelchair collision with obstacles during navigation of the wheelchair through a taught trajectory and allowing for close approach of the wheelchair to solid bodies present during performance of the teaching, and providing information about the markers from the proximity sensors and the cameras to the at least one computer. The method may yet further include the steps of operating the software to determine the location of various objects within a location, creating a path for the wheelchair to avoid the objects with the software, recalling the at least one taught path, and directing the wheelchair on the path via the software. 
   For the method described above, the method may include the steps of establishing ultrasound profiles at various junctures throughout a path during performance of the teaching, simplifying the profiles in a postprocessed computer event, and comparing the profiles during tracking through a taught path with current ultrasound sensed profiles. The method may yet further include the step of comparing disparities between the current ultrasound sensed profiles of objects to determine if a configuration of an object close to the taught path has changed since the teaching, and if the configuration has changed by a predetermined threshold, halting the wheelchair. 
   Additional features, advantages, and embodiments of the invention may be set forth or apparent from consideration of the following detailed description, drawings, and claims. Moreover, it is to be understood that both the foregoing summary of the invention and the following detailed description are exemplary and intended to provide further explanation without limiting the scope of the invention as claimed. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate preferred embodiments of the invention and together with the detail description serve to explain the principles of the invention. In the drawings: 
       FIG. 1  is a front perspective view of the computer-controlled power wheel chair of the present invention; 
       FIG. 2  is a partial front elevation view of the undercarriage of the computer-controlled power wheel chair; 
       FIG. 3  is a front elevation view of the computer screen on the computer-controlled power wheel chair; 
       FIG. 4  is a top plan view of a sample room showing the various paths; 
       FIG. 5  is a top plan view of a sample room showing various paths; and 
       FIG. 6  is a schematic chart of parallel user-interface processes. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   The computer-controlled power wheelchair navigation  10  is comprised of a wheelchair  20  with the traditional amenities such as a seat  30 , a back support portion  40 , arms  50 , a head rest  60 , elevating leg-rests  71  including foot rests  70  and leg supports  80 , front wheels  90 , rear wheels  100 , rear storage space  110 , and an undercarriage  120 . The wheelchair  20  is powered by a power supply such as batteries  130 . There are a variety of means available to control the wheelchair, such as a chin switch  140  shown in  FIG. 1 , however other conventional control means such as joysticks, buttons, voice control and etc, all known in the art, may be incorporated into the present system. 
   The wheelchair navigation system  10  also has at least one computer  150  that is seated in a computer docking station within the rear storage space  110 . At least one video camera  160  is connected to the computer  150  and aids in identifying the location of the wheelchair  20  when in use. Any of the video cameras  160  detect cues  170  that are strategically placed throughout a given location. Input to the navigation system&#39;s estimation algorithm in the computer  150  is provided by at least one digital shaft encoder  180  mounted at the wheelchair&#39;s drive wheel to sense wheel rotation, and by at least one monochrome video camera which detects wall-mounted cues  170  via video  160 . The cues  170  provide information to the computer  150  so that the computer  150  can identify the location of the wheelchair  20  and provide a pre-programmed or taught path for the wheelchair  20  to follow. 
   The basic components of a filter and a differential equation model of nonlinear dynamics of the wheelchair  20  combined with a sequence of incoming sensor information, wheel rotations and video images, produce ongoing best estimates of the position and orientation or ‘state’ of the wheelchair  20  in the two-dimensional space of the floor. 
   The computer-controlled wheelchair navigation system  10  relies on a unique ‘teach-repeat’ paradigm of control in which a person manually pushes the wheelchair  20  along each path to be included in the system&#39;s  10  repertoire. New destinations or routes of travel made obsolete by changes in the environment are easily ‘retaught’ in the same way. The system uses an estimator that is based on a Kalman® filter. The estimator is activated throughout the pre-programming or teaching episodes, and a compact record of the position and orientation histories of each trajectory is stored in the computer  150 , establishing a reference path for each desired destination. In subsequent autonomous navigation, the wheelchair navigation system  10  chooses the point toward which to steer based on the geometric relationship between the filter&#39;s current estimate of the actual position of the wheelchair  20  and the previously ‘learned’ reference path. 
   In one embodiment, inputs as well as the output voltage to the wheelchair controller  190  are interfaced with the computer  150 . All user input to the system is via a standard keyboard (not shown). Ultrasonic proximity sensors  162  are interfaced to a second computer  152  (not shown) which analyzes the time rate of change in the distance of near objects so as to assess the likelihood of a collision. The second computer  152  generates a digital proceed/halt signal serially interfaced to the full-sized navigation computer  150 . By continuously polling this signal, the navigation system  10  can bring the wheelchair  20  smoothly to a rest to avert collision with an obstacle, resuming travel along the reference path once the obstacle is removed. 
   The base for the navigation system is a commonly known wheelchair  20 . The wheelchair  20  can be adjustable and such amenities will not interfere with the wheelchair navigation system  10 . A pneumatic back support system  40 , adjustable headrest  60 , and elevating leg supports  80  may also be added to the wheelchair  20  to provide maximum flexibility with respect to riders with limited postural stability. 
   The wheelchair&#39;s undercarriage  120 , as shown in  FIG. 2 , provides the support base for the navigation system components. The undercarriage  120  accommodates the video cameras or sensors  160  which are mounted below the wheelchair seat  30  and positioned in such a way that their view is unobstructed by the rider when they are seated in the wheelchair  20 . The undercarriage  120  also houses, in addition to at least one wheelchair battery  130 , a separate battery  132  and a DC/AC inverter  200  for powering the components of the navigation system  10 . In this particular embodiment of the wheelchair navigation system, there are two 24 volt wheelchair batteries  130 , with an additional 12 volt separate battery  132 , however it is understood that various types and sizes of other batteries known in the art may be used within this system. 
   A second embodiment of the navigation system uses a single computer  150 . The computer  150  must accommodate interfacing with a variety of hardware components. The second embodiment also has digital encoders  180  and upgraded video cameras or sensors  160 . The second embodiment uses PCMCIA cards for capturing digital encoder signals, and for providing the output voltage to the wheelchair controller  190 . Since no suitable ‘frame grabber’ board having either a PCMCIA or USB interface can be found, the present system incorporates a full-sized PCI frame grabber, and interfaces it with the computer  150  via a docking station  210 . Video cameras  160  are serially interfaced to the computer  150 . 
   Navigation and obstacle detection software modules use various types of programming language such as C and C++, but are not limited thereto. The software module is also designed to run as ‘threads’ or processes controlled by the user interface software. At the same time, the navigation software is extensively modified to reflect the newly-modeled system dynamics of the wheelchair  20  as well as the upgraded components such as cameras and PC cards. 
   User interface software, such as Windows-95 based visual C++ programming is used in the present embodiment, however it is foreseeable that other comparable software can be used. The software enables the rider to control the navigation system  10  by speaking commands and/or switch activation. The determination of whether to commence navigation in voice or switch mode is made when the main software module is launched. 
   A dialog window  230 , shown in  FIG. 3 , governs which mode the navigation system  10  is going to operate in. Other characteristics of the rider&#39;s ensuing navigation session is input via a number of checked boxes, radio buttons, and a slider control shown in the dialog window  230 . The values of these controls are saved to disk in the computer  150  from session to session so that if the rider is using the chair with the same configuration of options as they used previously, an able-bodied individual may launch the main software module, ensure the rider has access to their switch and/or microphone, position the wheelchair  20  in such a way that it can detect its initialization cues  170 , and start the program. From this point forward, no further intervention on behalf of an able bodied non-rider is required other than perhaps to shut the system down after use and recharge the batteries, if such is not accessible to the rider. 
   In both voice and switch modes, feedback to the rider is provided by synthesized speech. For example, if the rider requests travel to a desk as a location, the computer will inquire if the rider is ready to engage the path ‘Desk’. The rider must always confirm their intention to travel with a specific command, either spoken or manually input, at which time motion along the chosen path commences. 
   If the rider issues a command not to travel, the travel is canceled leaving the rider free to select another destination. During travel, the rider may stop the travel of the wheelchair  20  by issuing a command to discontinue travel, such as to wait or stop. These commands interrupt the wheelchair&#39;s motion (without confirmation), and the chair  20  remains stationary until a command is issued for the wheelchair  20  to proceed. The rider is informed when the wheelchair  20  arrives at its final destination (or retraces its path completely back to its starting point) with a message that the travel has been completed. Such commands can be either audio commands or switch activated commands. 
   In the switch input mode, the rider wears either a headset or an earplug to facilitate aural scanning (not shown). In this mode, a text-to-speech (TTS) engine sequentially ‘speaks’ a list of available destinations or commands. When the rider activates the switch, the most recently articulated destination or command is selected. The speed with which the synthesized voice scans the rider&#39;s options maybe adjusted at any time during the navigation session by lengthening or shortening the pause separating each utterance. The scanning rate is set by a slider control  240  on the initial dialog screen  230  ( FIG. 3 ). This dialog window  230  also contains an options section wherein there is a box designated for scanning after a specified number of utterances  250  as well as another box designated to allow for sleep during travel  260  of the wheelchair  20 . If the sleep during travel box is checked, scanning is suspended once the rider chooses and confirms a destination, and motion commences. Otherwise, scanning is continuous during travel. In either case, the rider may suspend scanning at any time by issuing a command to shut the navigation system  10  down. 
   Once navigation has been suspended, either by explicit command or because travel has commenced, scanning can be resumed at any time by activating the switch. Any switch  140  may be used as an input mechanism for the device. Examples include but are not limited to: a bite switch (a small plastic pipette interfaced to a pneumatic switch), a sip-puff switch, a “twitch” switch, or any “universal” switch (stick, pillow, pneumatic cushion, etc.) which can be activated by virtually any part of the body. These switches  140  can be mounted to any part of the wheelchair  20  and may be swapped in and out of the system via a small modularized electronics or switch input box  220  ( FIG. 1 ) interfaced to the parallel port of the computer  150 . 
   In voice mode, the rider wears a headset with a small microphone (not shown) which are commonly known in the art. A voice recognition computer program, also commercially available, is used to facilitate the spoken commands. Prior to operating the navigation system by voice for the first time, the rider must “train” the speech recognition software to recognize their individual voice. Nevertheless, the navigation system user interface software provides for optional supplementary switch input to handle recognition errors. For example, if the check box “Scan after 4 unrecognized utterances”  250  is left unchecked on the setup dialog window  230  ( FIG. 3 ), unrecognized speech, such as conversation, is ignored by the navigation system  10 . If this box  250  is checked, the system will respond to each unrecognized utterance with either a voice then synthesized message or a typed response that the command is unclear. Then the computer  150  will either prompt the rider for another command, or wait until another command is given. After a series of unrecognized utterances (i.e. three if the number of utterances is set for four), the software can “read” to the rider a list of available destinations. After yet another a unrecognized utterance (i.e. the fourth), the software enters scanning mode and the rider makes their selection via switch activation. After a successful selection by switch, the software returns to voice mode. Regardless of the status of the options box  250 , 260 , the rider has the option to suspend voice recognition any time by rendering a command for the system to close down. Once suspended, the navigation system user interface software will only respond to a pre-selected activation command (i.e. the spoken word “Navigate”), which reactivates the voice recognition. As a final feature in voice mode, the rider may elicit an aural listing of the available choices at any time by asking for their options. 
   The rider is also capable of changing between the voice and scanning modes. This is facilitated by another options box  290 , labeled “Allow mode changes” on the setup dialog screen ( FIG. 3 ). Therefore, as conditions vary the rider can direct the navigation system either verbally by spoken words or by switch activation. This feature is optional since not all riders will be able to use both modes. In other cases, the rider may have a preference for a given mode but may choose to change modes when they encounter changing conditions. The rider changes operating modes in the same way that other commands are issued: by manually selecting the specified mode while scanning, or by speaking a designated phrase identifying the scanning mode while in voice mode. The rider may move between operating modes as often as desired. 
   The rider may use the dialog window  230  as an aid in identifying the various destinations known to the navigation system  10  by viewing a box  310  listing a tree structure list of the various destinations. Names at the root level may represent separate environments (i.e. home). The next level of destinations may represent rooms or other areas of interest within the given environment (i.e. the kitchen), with the lowest level representing specific locations within rooms or areas (i.e. the sink or stove). 
   Using this tree structure  310 , only destinations reachable from a given location are available when the rider is at that location. For example, if the rider is in the kitchen at home, the elevator at work is not an available destination. This type of organization produces the shortest possible list of options to scan in switch mode, and minimizes recognition errors in voice mode by limiting the active vocabulary to a logical subset of possible destinations. It also allows use of destination names that would otherwise be ambiguous. For example, there may be a table in the rider&#39;s kitchen as well as in their bedroom. Knowledge of the rider&#39;s current location resolves the ambiguity. If paths have been taught in multiple environments, the environment for the ensuing navigation session may be chosen from the drop-down box  320 . 
   With the first embodiment, initial position estimates were either entered manually from the keyboard or were read from the first path file to be executed. This demanded exact placement of the wheelchair  20  at these coordinates prior to commencing travel, an inconvenient and potentially difficult task with a rider in the chair. Therefore, an additional software module can be used to estimate the wheelchair&#39;s initial position based on each camera&#39;s  160  ability to locate a unique configuration of cues  170 . To enable autonomous navigation for the rider, the wheelchair  20  need only be placed anywhere in the vicinity of these cues  170  when the main software module is launched. 
   One of the first tasks of the locator module is to call the initialization routine in a loop. If either camera  160  cannot detect its initialization cues  170 , the caregiver/attendant is notified accordingly by both a synthesized voice message and a message box (not shown). The message instructs the rider to verify that the cameras  160  are turned on, to ascertain that the cues  170  are not obstructed, and if necessary, to reposition the wheelchair  20 . Having done so, the caregiver/attendant merely touches a key to repeat initialization. 
   It may be possible for the rider to control velocity of the wheelchair  20  with commands. However, it may also be controlled automatically by the navigation algorithm which slows the chair when position estimate errors are high, so that it may process more video information per inch traveled. The navigation algorithm may increase speed gradually as estimates improve. 
   The rider also has the ability to stop the wheelchair  20  completely and then either continue along the selected path or retrace the path back toward its starting point. 
   If a conversation takes place within the vicinity of the wheelchair  20 , the rider may suspend the voice activated user interface to prevent speech recognition from being confusing, or so that those in the conversation will not be distracted by continued aural scanning. The wheelchair  20  may remain stopped for any length of time, and may continue along the selected path simply by the rider issuing a command to continue. 
   Alternatively, the rider may issue the command to go back, and the wheelchair will commence retracing its path. Hence, the rider may change their decision of travel to a particular destination at any time and return to the point of departure. The command to go back or return is also useful if the rider has issued a command to stop late in the process, and has actually passed the point where they wished to stop. After issuing the command to go back, the rider may back up to the desired stopping point, issue a command to stop again, and then continue at the rider&#39;s discretion. This combination of features, in effect, provides a virtually infinite number of destinations along taught paths. 
   It should be noted that the halt command is intended only for the rider&#39;s convenience and operating functionality. It is recognized that any rider in any particular situation may or may not have the ability to stop the wheelchair  20  quickly enough to avoid an obstacle. The chair&#39;s proximity sensors  162  are intended for this purpose. 
   The original navigation software of the first embodiment is provided for execution of only one pre-programmed path at a time. With the updated software of the second embodiment, if no pre-programmed path exists between the rider&#39;s current location and the requested destination, the system seeks to construct a path by joining first two, then three, then four or five pre-programmed paths. The shortest possible path is constructed, and the process is seamless to the rider. 
   The navigation system also has a utility that takes an existing pre-programmed path and creates a new path with all segments reversed. This utility and the path joining capability are of significant benefit to the rider and their caregiver since it is no longer necessary to teach or pre-program a specific path from each location in the environment to every other location in the environment. The utility becomes increasingly important as the number of locations increases since the number of possible paths connecting n destinations is n*(n−1) (i.e. 90 paths for 10 destinations). 
   The path utility is only appropriate in certain circumstances since the rider does not generally wish to travel in reverse. However, the placement of furniture and fixtures together with the need for a specific terminal orientation of the wheelchair  20  may dictate that the most expedient route of travel is in the reverse. This is particularly true when distances are short. For example, in  FIG. 4 , the best route from the desk D to the window W may be the reverse of the path from the window W to the desk D. Similarly, if the chair is at the couch C, there may be insufficient space to turn the wheelchair  20  around so the best path to the window W is in reverse, and the most expedient path to the desk D is to back up to the window W and proceed to the desk D using the path already taught (path W-D from the window W to the desk D). 
   If all these conditions were true, the six possible paths connecting all three destinations W,D,C are implemented by teaching only the two paths shown, path W-D and path W-C. Even when the path reversal utility is not appropriate, the path joining capability may significantly reduce teaching time and effort, depending on the geometry of the environment and the fact that paths may be taught to intermediate locations which are not true destinations of interest. 
   As shown in  FIG. 5 , a person other than the rider may teach or pre-program paths to an intermediate node X which is central to four desired locations W, D, C, T. With path joining, all 12 possible paths between these four locations may be realized using only the 8 pre-programmed or taught paths shown, X-T, T-X, X-C, C-X, X-D, D-X, X-W, and W-X. 
   As previously discussed, the first embodiment has navigation software running on a computer  150  interfaced with a second computer  152 . The second computer  152  runs obstacle detection software. All user input to the system is done via a keyboard. 
   The second embodiment has a single computer  150 . The main module has a user-interface (U/I) thread which, after all setup and initialization functions have been performed, the thread monitors the microphone or switch for user commands. Once the rider has selected and confirmed a destination for travel, the U/I thread initiates the navigation thread which, in turn, initiates the sonar thread for obstacle detection. During travel, the U/I thread continues to monitor the microphone or switch in the event the rider wishes to stop the wheelchair  20 . When travel is completed, the navigation and sonar threads are suspended until the rider requests further travel. Under these circumstances, resources are consumed only as needed, ensuring maximum responsiveness of the user interface to the rider&#39;s actions. The threads communicate with each other by setting and reading a status variable.  FIG. 6  represents a schematic chart of these parallel processes. 
   The navigation system  10  can navigate through an area using a single camera  160 . However, by using a single camera  160 , the system&#39;s position estimates are increasingly uncertain, which causes the wheelchair  20  to reduce speed. This could occur at precisely the moment more power is needed to cross from one location into another (i.e. from linoleum to carpet). To solve this problem, when the wheelchair  20  fails to produce nonzero wheel rotations for a specified number (i.e.  200 ) of consecutive processing cycles, a brief burst of power is delivered to the wheelchair controller  190 , enabling the wheelchair  20  to overcome its inertia. This refinement allows the navigation system to reliably transition from one location to another location which may have a different type of surface (e.g. tile vs. carpet). 
   Errors in the system&#39;s position estimates are calculated from video images in units of pixels. If an error is within a given tolerance, the location of the identified cue  170  is incorporated into the algorithm&#39;s estimate of the chair&#39;s position. If not, the cue  170  is rejected and the position estimate incorporates only odometry information (dead reckoning). Since the cameras  160  are close to the cues  170  in certain situations such as a narrow hallway, errors in this region are magnified to such an extent that the wheelchair  20  is forced to dead reckon even when cues  170  are properly identified. The generalized solution to this situation is to associate dynamic error tolerances to individual path segments within the files that define each route of travel. 
   Initialization cues  170  are strategically placed within a specific location wherein all travel within that location commences from that starting point. A variety of paths are pre-programmed in this location. 
   The current navigation system is a vision-based system in which video detection of wall-mounted cues  170  is combined with odometery information to obtain accurate ongoing estimates of the wheelchair&#39;s position and orientation. 
   The navigation software sends to the power wheelchair controller  190  a signal simulating that of a joystick and guides the wheelchair  20  accurately along paths which the system has previously been pre-programmed or taught by an able bodied human instructor. The ‘teach-repeat’ paradigm of control, in which human teacher manually pushes the wheelchair  20  along any desired route of travel, obviates the need to fully characterize the geometry of the environment. Such characterizations, normally required for automatic trajectory planners, are difficult to acquire and maintain. The navigation system&#39;s  10  only use of ultrasound is to detect near obstacles with which it might otherwise collide. 
   The navigation system provides fully autonomous navigation. That is, the principal responsibility for steering is delegated to the navigation system  10  with the rider retaining the ability to, at their own discretion, halt and resume travel, or halt and retrace the current path toward the point of departure. 
   Because the paths are pre-programmed or taught by a human instructor, they readily incorporate close approach to furniture, passage between objects with minimal clearance, and complex motions such as the multiple changes of direction required to maneuver into tight spaces. The human judgment inherent in the original teaching episode is brought to bear in each repetition of the taught path. 
   The present system extends existing theoretical development for making use of a sequence of incoming, imperfect information combined with a nominal, also imperfect, differential equation model of the ‘plant’ or system, to produce ongoing best estimates of the ‘state’ of the system. For nonlinear system dynamics such as those of a motorized wheelchair, a numerical-integration-based filter is used, and described in detail in the article “An Autonomous Vision-Based Mobile Robot,” by E. T. Baumgartner and S. B. Skaar. Because only nominal kinematic rather than kinetic equations are used, the navigation system  10  dispenses with time, the usual independent variable, and uses instead a kinematic independent variable: the average forward rotation of the two actuated drive wheels  100  of the wheelchair  20 . Since time is no longer the independent variable for control, new means of advancing forward along the reference path must be devised. As with human control of vehicles, it has proven possible and natural to advance the ‘target’ juncture on the reference path via estimated location rather than time. That is, the point along the path toward which to steer is chosen based on the geometric relationship between the current estimate of actual position and the previously ‘learned’ reference path. 
   Several advantages attend the use of forward average wheel rotation as the independent variable. First, since the differential equations are now time-independent, it becomes convenient to control the speed of the vehicle entirely independently of the estimation and tracking algorithms. Hence, vehicle speed may be altered in response to any set of conditions without affecting the position-estimation or tracking algorithm. 
   Secondly, the vehicle will not ‘cut corners’ which could jeopardize rider safety in order to “catch-up” with the time-based reference. 
   Finally, the rider may choose to assert manual control of the wheelchair  20  at any time, taking it from the actual reference path. Since the system&#39;s estimator within the computer  150  is activated whether or not it is in control of the chair&#39;s motion, and since the control loop is time independent, the navigation system  10  is capable of re-engaging the target path without resorting to any special estimation or control algorithm even though an unplanned detour takes the wheelchair  20  some distance away. 
   Wheel rotation measurements are taken by the digital shaft encoder  180  and supplemented by observation of visual cues  170  placed in convenient locations throughout the environment of interest. Use of these cues  170  offers a major advantage over the more commonly used ultrasound or sonar in that the ‘signature’ of the image is distinct, and the frequency of corroborating input is high; hence, there is negligible danger that the system&#39;s estimator will become ‘confused.’ Also, any number of navigation vehicles  20  may navigate the same environment, referencing the same cues  170 , without interfering with each other. 
   The rider may control the navigation system by a single, discrete input such as a spoken word, activation of any simple switch, or touchscreen input. The system provides feedback to the rider via synthesized speech, visual cues, or aural cue. To facilitate path selection, destinations known to the navigation system are stored in a data structure such that only the destinations reachable from a given location are available when the rider is at that location. Once the rider selects an available destination and confirms their intention to travel, motion along the chosen path commences. During travel, the rider may use their input device to assert such supervisory functions as influencing travel speed, halting motion at any point, resuming the original reference path, changing destinations, retracing the path to return to the point of departure, or reasserting manual control of the wheelchair, to the extent the rider is able. 
   In order to avoid unforeseen obstacles that (by definition) were not there when the tracked trajectory was taught, ultrasonic proximity sensors  162  may be used as described below. Specifically, as described above, sensors  162  may be interfaced to second computer  152  (not shown) which analyzes the time rate of change in the distance of near objects so as to assess the likelihood of a collision. The second computer  152  generates a digital proceed/halt signal serially interfaced to the full-sized navigation computer  150 . By continuously polling this signal, navigation system  10  can bring wheelchair  20  smoothly to a rest to avert collision with an obstacle, resuming travel along the reference path once the obstacle is removed. 
   In order to further utilize sensors  162 , enabling use can be made of the record of ultrasound readings acquired during trajectory teaching in order to permit discrimination between actual obstacles and solid objects that are simply in place (were in place during teaching) but that are not a concern with respect to the trajectory currently being tracked. 
   In this manner, ultrasound sensing may be applied to avoid collisions with obstacles while at the same time allowing for the close approach to solid bodies as part of the trajectory objective (e.g. approaching an appliance in the kitchen or bathroom, or approaching a bed.) 
   In this regard, in addition to the aforementioned vision-based repeat strategy, the “teach-repeat” disclosed herein may entail the use of complementary ultrasound sensing by means of sensors  162  in an important and essential way, for many real-world applications. Unlike any prior art teach-repeat strategies or the teach-repeat strategy disclosed above, ultrasound sensors  162  may be operated during teaching, not simply during tracking, in order to avoid obstacles. While the existing disclosure of Steven B. Skaar “Extending Teach-Repeat to Nonholomonic Robots,” Structronic Systems, 1998, 316-342, does mention using proximity sensing including ultrasound as a supplement to vision for pose assessment during both teaching and tracking, this is not the implication of the disclosure herein, and indeed use of the ultrasound data during teaching serves a very different purpose from this: Ultrasound signals from sensors  162  are well known to create imprecise representations of the current surroundings due to such sensor attributes as specular reflection. However, given similar sensor/object juxtapositions, signals from ultrasound sensors  162  are highly repeatable. Use of sensors  162  during teaching, then, is an excellent way to ensure that in the immediate vicinity of travel objects before wheelchair  20  during a tracking or “repeat” event are as they were when teaching occurred. 
   The aforementioned feature of ultrasound sensing during teaching is therefore particularly enabling when the task requires very close approach to a solid object such as when nearing a bathroom fixture. Moreover, the aforementioned feature of ultrasound sensing during teaching is by definition a strategy unavailable outside of the teach/repeat approach to navigation. 
   Based upon the aforementioned, during motion of wheelchair  20 , ultrasound sensors  162  may be used to avoid obstacles as wheelchair  20  proceeds through its taught trajectory. Obstacles, including humans or animals, may be introduced in the path of wheelchair  20  after teaching and thereby interfere with execution of a taught path. Ultrasound sensors are inexpensive proximity sensors capable of automatically determining the distance between the sensor and the closest solid object. Given that wheelchair navigation system  10  as part of its operation keeps track of the current coordinates of wheelchair  20 , including those when the ultrasound pulse is emitted, and given that the path being executed has already been taught and is therefore known to the controlling computer, it would follow that signals from sensors  162  would be sufficient to compute whether continued execution of the path should result in collision. However, properties associated with ultrasound do not support this simple conclusion. In practice, the well-known specular reflections of ultrasound echoes, together with the progressive spread of the emitted sound reduce the accuracy of any such calculation. Combined with the fact that many of the practical paths or trajectories of interest may require close proximity to solid objects this fact precludes this simple use of sensors  162 . 
   Nevertheless, there is a synergy between the teach/repeat operation of the basic navigation capability and the application of ultrasound for effective obstacle avoidance. This synergy is based upon the fact that ultrasound responses where sensors are similarly placed with respect to solid objects of the same geometry are highly repeatable. As a consequence, with regard to the aforementioned teach-repeat strategy, there is the prospect of using the teaching event to establish ultrasound profiles at various junctures throughout the current path. These profiles are simplified in a postprocessed computer event and compared during tracking with the current ultrasound profiles. It is significant disparities or discrepancies between the local (to the path segment in question) profiles that becomes the criterion for determining whether or not it is likely that the configuration of objects close to the taught path have changed significantly since the teaching event. 
   If there has been such a change, and if the aforementioned calculation indicates a nearing of near-future path to any such new object, then the probability of contact of wheelchair  20  with the object can be regarded as high. Such a means of tolerating very close proximity to unchanged objects while avoiding new, introduced bodies is critically dependent upon the teach/repeat mode of navigation. Additionally, in the event that autonomous system  10  determines that the probability of contact is too high to continue, another capability of teach/repeat can be drawn upon: Once system  10  halts forward progress along the path in order to prevent contact, it is then able to identically reverse its progress along the portion of the path executed up until the point of coming to rest. This is essentially a reversal of all previously executed motions and its feasibility is guaranteed provided, over the short time period since the current tracking event began, no additional obstacles were introduced to block that recently executed portion. 
   Ultrasound sensors  162 , provided their location is permanent, may be placed at any locations on wheelchair  20 . This results in a virtual shield for the rider without the impractical consequence of being unable to execute the wide range of potentially crucial motions that entail close approach to various solid bodies such as sinks, toilets, furniture, doors and so on. 
   Although particular embodiments of the invention have been described in detail herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those particular embodiments, and that various changes and modifications may be effected therein by one skilled in the art without departing from the scope or spirit of the invention as defined in the appended claims.