Object Recognition
Pertaining to Object
Perception and Object Navigation
(Robotic navigation simulation, using Java)
Dr. Pei Wang
Artificial Intelligence, Temple University
CIS 203
developed by
James Butler
December 11, 2004
Object Recognition
Object
Recognition
Object Perception
Object Navigation
Planning
Scheduling
Executing
Monitoring
Ideas and Concepts behind the Robot Simulation Program
Overview
Robot Simulator
Robot Controller
Robot Perception
Robot Memory
Using the Program
Program Instructions
Current Issues
Fixes and Updates
Remaining Development Issues
Resources
Object Recognition in an environment applying Artificial Intelligence requires the use of optical sensors to scan the immediate area within the sensor's range. Using the image light reflects back to the sensor and a 3D image development equation, a 3D outline of an object's image can be formed and identified through a Neural Network structure. Likewise, an image data structure could be built and an image matching algorithm written to compare images stored within the image data structure with those returned by optical sensors. However, using an image data structure typically requires more resources than an image Neural Network. An image Neural Network is a predefined or learned image matching algorithm. Whereas, using an image data structure requires both an image storage structure and an image matching algorithm. Hence, taking the time to build an image Neural Network may be well worth the extra time and effort to develop in the long run, especially if an Object Recognition System (and any future Object Recognition Systems) involves identifying a wide range of objects.
In the context of image recognition, only a general, non-detailed, 3D outline of an object is often necessary. And, while detailed image recognition is often required for object manipulation, it may be more useful to identify objects with general 3D patterns when object manipulation is not required; matching general 3D patterns may prove more useful in matching a wider range of similar objects each with different features than attempting to match a full range of an object's features not necessary for object recognition when object manipulation is not required. The objective is to identify objects with the level of detail required to perform an accurate match for a given function or objective. If identification of specific features are required, then they must be included in the recognition process. Otherwise, identifying objects through general matching patterns are often more efficient, easier to implement, use less resources and hold a higher probability of accuracy, since specific matching may result in unsuccessful results, and this when specific detail is not even essential to the objective.
Object Perception is an extension of Object Recognition in that it involves learning something from the recognition of objects within its environment. Is the object observed of some importance? If so, what is the importance of it? Should there be some response to the observance of an object? If so, what are the possible responses? Object Perception learns from its environment and forms the basis for responding to it and to changes within it. In AI, perception is the identifier of conditions to which some response may be required. When a condition is perceived to require some action, actions are performed based on a set of rules, steps or procedures to handle the event or condition. Moreover, perception often involves learning the means to respond to events or the means to correct or improve upon methods for handling them. Often, in the process of handling an event, or in the moments thereafter, a more efficient means for handling the event is perceived. In AI, an Object Perception System may include, Heuristic Searches, Production Systems, Expert Systems, Case Based Reasoning Systems, Reinforcement Learning Systems, Probability Reasoning, Fuzzy Logic Systems, Concept Learning Systems, Inferential Learning Systems and Anytime Algorithms.
Object Perception involves memory. Perceptive learning incorporates some previous understanding and/or knowledge of the subject of interest. How do you perceive something if you don't already have some idea of what it is you perceive? How can you perceive a better way of doing something if you don't already have some knowledge or understanding of what is you are doing? Knowledge and understanding are information retained in memory. How do you know where the kitchen is in your house or apartment? Most likely you know where it is because you have been there before (a prior experience) and information about how to get there is stored in your memory. How do you know there is not a faster way to get to your kitchen? Most likely it is because at some point you walked through your house or apartment and learned where were all the rooms and all the ways to get to them. Again prior experience is stored in memory, and in many instances this knowledge is accessed subconsciously, without your realization. Likewise, perception typically involves prior knowledge of a given event and some usual possibilities for handling it. How else do we perceive an event has occurred and what the possible responses to the event may be? Hence, in order for an Object Perception System to have a high level of perception, it must also have a high level of memory and an effective means for accessing it.
Object Navigation requires a high level of perception about the environment within which navigation occurs and a high level of knowledge about objects being navigated or being navigated among. Primarily, navigation requires information about the object, time, space, distance and methods for navigation. The level of information required for navigation depends on the complexity of the navigation. Knowledge and perception of the object and its environment aside, key to effective navigation is an adequate system for navigation. An adequate system for navigation provides a thorough list of methods for all realistically feasible means of navigating objects or for navigating among all realistically feasible objects and obstacles.
Consider the simple task of navigating along an unknown path in order to reach some place of interest. How do you know which way to travel along the path? If you make a wrong turn, should you be able to reverse your course? And, if later you perceive you shouldn't have reversed your course, should you then be able to reverse you course again? And then again, and again and again? How many times should you be able to reverse your course? In deciding this issue in my Robot Simulation program, I thought it was best to allow unlimited reversals. My reasoning was as follows: If the chosen direction is in fact incorrect, then reversing direction is the wisest choice. If the path to a place of interest is unknown, then not allowing unlimited reversals may result in failure. The reasoning for this is simple. If at any time the ability to reverse course is limited, and the current direction is wrong, regardless of the number of previous reversals, then the effectiveness of eventually discovering a path to the place of interest is reduced, if possible at all. The only exception to this reasoning would be when a path in some direction is known, for certain, to be wrong, based on some prior experience.
The point I'm attempting to make is simple. Navigation options should only be limited by the certainty that the option is not valid or reasonable given absolute facts, and if uncertain about whether to allow some method of navigation, then allow it, providing it will not perform some hazardous event. If an appropriate learning system has been provided, then removal of a navigation method can always be implemented when facts are certain as to its effectiveness. In conclusion, navigation is a very complex process involving a high level of information and detail about navigating specific objects and navigating among other objects in or possible within the given environment. Navigation is further discussed in several other areas of this document.
Planning pertaining to Robotics involves defining rules of operation within the realm of possible events, situations or conditions. Particularly pertaining to my Robot Simulation program, planning consists of setting constraints such as boundaries around objects where within which navigation is not feasible and eliminating movement in a direction blocked by an object's boundary; it involves defining all the possible methods of navigation for every possible condition in every possible environment. Details pertaining to objects within an environment are recorded in memory and accessed to build conditions essential for robotic navigation. As the environment changes, details about the changing environment are compared against the conditions defined and actions are taken according to the results of these comparisons and the actions possible given the condition. In the Robot Simulation program, primary conditions involve the distance of the robot relative to objects in its environment and its location relative to the location of objects of interest, mainly doorways, the entrances to other rooms, or the object required to complete the mission -- the stove or washer.
Scheduling is an essential robotic activity for executing robotic activities in response to the occurrence of an event. Scheduling involves defining the order and timing within which activities are required as events and conditions occur within a given environment (Wang, Robot and Agent). All activities are performed in some kind of order, based on evolving conditions in an ever changing environment. The order itself may be optional, meaning there may be more than one activity possible for any given event, but there is still an order to which even optional activities must be followed. Scheduling involves defining the order for all feasibly possible activities for all feasibly possible events occurring within the ever changing robotic environment. Scheduling occurring within the Robot Simulation program mainly occurs within the Robot Perception subsystem and is covered in detail in the Robot Perception subsection of the Ideas and Concepts behind the Robot Simulation Program section.
Execution is the implementation of activities as programmed or scheduled in response to the realization of conditions arising from the occurrence of events within the robotic system's environment (Wang, Robot and Agent). It is the implementation of activities in a defined but perhaps selective order in response to conditions and the events giving rise to them. It is the actual navigation of and navigation among objects within a robotic system's ever changing environment. A robotic system's Controller subsystem executes activities as they are determined by the Perception subsystem. The Perception subsystem is responsible for evaluating events against known conditions and for initiating responsive actions for the Controller to execute. Execution of the Robot Simulation program is mainly run from the Robot Controller subsystem and is covered in detail in the Robot Controller subsection of the Ideas and Concepts behind the Robot Simulation Program section.
Monitoring events is a key activity occurring within Robotic systems. Robotic systems require a constant influx of information about its operating environment. Sensors constantly monitor the surrounding environment and feed information into the system. The system processes this influx of information, evaluating it against conditions requiring some form of action. Furthermore, as a robotic system navigates within an environment, the environment changes as a result of the robot's actions. Every change in the robotic environment must be monitored so changes can be evaluated against conditions requiring responsive action. A robotic system's Perception subsystem is responsible for evaluating events against known conditions and for initiating responsive actions for the Controller subsystem to execute. In real life applications, changes occurring within the robot's working environment will not be known by the Robotic system directly. Changes occurring within the environment are read by sensors and fed into the Robot Perception subsystem for evaluation and action determination. Monitoring occurring within the Robot Simulation program mainly occurs within the Robot Perception subsystem and is covered in detail in the Robot Perception subsection of the Ideas and Concepts behind the Robot Simulation Program section.
Ideas and Concepts behind the Robot Simulation Program
When an assignment is selected from the simulation Command Pane, the simulation program begins by moving the robot in an obstacle free direction toward the location of an object of interest, an entrance to another room. At locations where a turn is required, a turn in an obstacle free direction is randomly chosen, and the robot proceeds in a direction toward its new target, the entrance to another room or the object required to complete its mission. Each direction and turn is temporarily recorded in a three column path array, along with the room from which these events occur. Additionally, a count of the number of turns is kept. Upon either successfully completing the mission or reaching the maximum number of allowed turns, 30, the number of turns is compared with the number of turns for the shortest path found so far for the mission. If this number of turns is less than the number of turns for the shortest path so far, then the robot's memory structure, a linked list with a double path's array, is updated with the information from the temporary array, and the turn count is recorded in the linked list's count field. Nodes in the linked list are created and accessed by mission names and optionally by an event ID code. Each node additionally contains the path array for recording the path, turn and direction taken and a count field for recording the number of turns. When a path has been found for a mission, users can then select to run the best path found so far for the mission, and the program will run the path according to the order defined in the path array.
The Robot Simulator interfaces with users through the Robot subsystem (class) of the Robot Simulation program. Users select options from the Command Pane. Options for exiting the simulation, restarting the simulation, and increasing or decreasing the robot's speed are implemented from the Robot subsystem. Otherwise, the Robot subsystem calls the Robot Perception subsystem to initiate the mission or assignment selected from the Command Pane. The Robot Perception subsystem is responsible for evaluating the robot's working environment, for recording details about the environment, for initiating responses to conditions arising within the robot's working environment and for interfacing with the Robot Memory subsystem to access and store details about environments engaged and the activities performed within the environments. The Robot Perception subsystem determines what activities are required for completing requested assignments and then passes control to the Robot Controller subsystem for execution. The Robot Controller subsystem interprets instructions received by the Perception subsystem and then executes these instructions accordingly. In the Robot Simulation program, the Controller subsystem informs the Perception subsystem it has completed an instruction by calling methods within the Perception subsystem that reevaluate the environment and indicate the next required course of action. The Perception subsystem reevaluates the environment for changes occurring within it, such as the robot's position relative to conditions (or decision points) within the environment, determines the next course of action, informs the Controller subsystem of the action required and returns control to the Controller subsystem for execution. Details pertaining to using the Robot Simulator are covered in the Program Instructions section. Details pertaining to the Robot Controller, Robot Perception and Robot Memory subsystems are cover below under their respective subsystem names.
As previously described, the Robot Controller subsystem interprets instructions received by the Robot Perception subsystem and then executes these instructions. In the Robot Simulation program, the Controller subsystem informs the Perception subsystem it has completed the instruction by calling methods within the Perception subsystem that reevaluate the environment and indicate the next required course of action. The Controller subsystem actually queries the Perception subsystem to determine in which direction the robot should navigate after the initial or previous move in a given direction. If the Controller's query does not return a direction for navigation, this means that conditions have not been met that allow movement in any given direction -- a target boundary has been reached and a turn in a new direction is required. At this point, the Controller subsystem returns control to the Perception subsystem so navigation in a new direction can be determined as required. This process is perpetually repeated after each incremental movement, or non movement, until the mission has been accomplished.
The Perception subsystem evaluates the environment after each robotic movement and then determines the next move the robot should take. The Perception subsystem returns the result of the Controller's query, indicating whether the robot should move in the direction queried. The robot can move in any direction as required to accomplish its objective. However, incremental movement in the up-right, up-left, down-right and down-left directions have been predetermined for the environments in the simulation. In real life applications, the incremental movement in any of these directions would have to be determined from within the existing environment and set accordingly by the Perception subsystem. The robot can, however, navigate in any given direction -- up, down, left, right, up-right, up-left, down-right, down-left -- within parameters meeting conditions requiring a new course of action. These parameters indicate the locations of doorways (room entrances), the location of devices used in completing the mission, (washer and stove) and the boundaries of objects within the environment (the constraints on navigation).
The Robot Perception subsystem is the meat and potatoes of the Robotic Simulation system. It is responsible for evaluating the robot's working environment, for recording details about the environment, for initiating responses to conditions arising within the robot's working environment and for interfacing with the Robot Memory subsystem. The Perception subsystem interfaces with the Memory subsystem to access and store details about objects, events and circumstances engaged within each environment and to access and store activities performed within each environment. The Robot Perception subsystem defines activities based on information attained from the environment and from the Robot Memory subsystem. It then passes control to the Robot Controller subsystem for execution of the activities.
The Perception subsystem records the position of essential objects in each new and evolving environment, determines navigational boundaries for each object in the environment, records the location of objects of interest, determines constraints, targets and decision points where actions are required, determines the activities associated with each possible event and accesses the Memory subsystem to store and obtain data required for making decisions and to store and obtain data on objects and events engaged in the environment . Obviously some of these areas overlap and some of these activities are not required for every object in the environment. Only essential objects need be identified and plotted, and activities only need be performed one time for each changed environment. Some objects only require an initial identification according to their relevance in a changed environment. While other objects, such as the robot's position relative to other objects in its surroundings, need to be continuously identified and plotted with each change in the environment.
Ideally, the Perception subsystem may consist of only a list of all possible events or activities realistically possible within a given environment, listed by name. Procedures for determining a course of action would then be written as individual classes, and when an event occurs requiring an activity, an instance of the appropriate event/action class is instantiated and implemented for activity determination. The list of event/activity names could be stored in the Memory subsystem and accessed as required by the Perception subsystem. However, this is not the way the Robot Simulation program is written for a number of reasons, but mainly because of the complexity involved in writing it and the additional and unnecessary drain on system resources. Instead, the processes for determining courses of action are written as methods within the Perception subsystem.
In the Robot Simulation program, the Perception subsystem initializes the Memory subsystem with the coordinates and decision points for navigating the robot among objects and towards objectives, or targets, within each environment. The coordinates not essential for navigation are not included in this initialization process, meaning the coordinates of most objects are not included in memory. The Perception subsystem also sets-up the required fields for painting the room images for the simulation program and then instructs the Image Painter Manager to paint the images. While the Perception subsystem tracks the positional location of the robot as it navigates within its environment, it stores this data in the Image Manager Painter, since it requires this information to paint the robot's position within the room image. In real life applications, an Image Painter would not be required, and this data would be stored in fields within the Perception subsystem; fields are provided for storing this data, however, they are not used in this Robot Simulation application. In correlation to tracking the robot's position, the Perception subsystem evaluates the robot's position to determine if a parameter condition has been met, requiring a new plan of action (a change in direction in this simulation program). If one has been met, the Controller's query will return with no instructions to implement, and it will return control to the Perception subsystem so it can determine a new course of action (a change in direction in this simulation program). Parameter conditions include the locations of doorways (room entrances), the location of devices used in completing the mission, (washer and stove) and the boundaries of objects within the environment (the constraints on navigation), as previously mentioned.
For perception to have value, especially pertaining to object navigation, at least three type of determinants are necessary. They are a point from which measurements originate (an origin point for calculating and measuring distances) the point of the robot's current position (the current position of the robot) and the point where decisions are essential (the boundaries and locations of objects and objects of interest in the environment). In the Robot Simulation program, the origin point is the first point in the image panel, (0,0). All measurements of objects within the panel are based on their relation to the origin point of the panel which contains them. The robot's current position begins at one of the entrance points (doorways) within each new environment (room image within the panel) then moves in the direction determined to reach an identified target (doorway or device) with the environment. Within each environment (room image) the Perception system must identify and record the position of targets for the robot to navigate towards. The location of these targets are the decision points (also considered boundaries or constraints) in the environment, and are the points at which some action is necessary for the robot to proceed on its mission. Below is a graphical diagram illustrating how points within the image pane (the robot's environment) are plotted and related to the origin.
The primary function of Robotic Memory subsystems is to store data essential for performing robotic activities. While its function appears small, its value is immeasurable in Robotic systems, especially considering the complexity of real life Robotic systems and their applications. As previously mentioned, Robotic systems are in many ways only as useful as the depth of their Memory subsystems. Memory subsystems are invaluable components of Robotic Perception applications and Robotic functionality. Without sufficient Memory subsystems, Robotic systems have limited to little perceptibility and functionality, if any at all.
The Robot Simulation's Memory subsystem consists of a linked list with a double array for recording activities, a single array for recording other values (not used in this simulation program) and fields for identifying nodes, linking and counting. Nodes in the linked list are created, identified and accessed by names and optionally by an event ID code (also not used in this simulation program). In the Robot Simulation program, nodes are identified by mission names. Activities are identified by the row index of the double path array, where the row index corresponds to the activities performed within an environment at each decision point. Each row in the activities path logs the environment ID (first column), the activity performed (second column) and the next navigational direction (third column). The environment ID is the room ID where the activity occurs; the activity performed is a change in direction, and the next navigational direction is either up, down, up-right, up-left, down-right or down-left. Strict right and left directions were not used in the simulation program, so they were left out of the direction parameters. However, methods are in place for navigation in all directions, including right and left directions.
Additionally, the Robotic Simulation's Memory subsystem stores the coordinates for the robot's starting and ending positions within each room, along with the decision points determined for each room. For example, memory.setArray(LIVING_RM,342,606,430,606,342), where the first column is the room ID, the second column is the decision point and the remaining columns contain the coordinates of the robot's starting and ending horizontal and vertical positions relative to image panel's origin coordinates. While this example only shows coordinates for two positions, there are actually several ways object coordinates could be stored in the Memory subsystem. Several methods have been provided for creating and accessing the nodes and node arrays within the Memory subsystem. Below is a graphical diagram of the Robot Simulation's Memory subsystem. The actual areas of the Memory subsystem used in the Robot Simulation program are highlighted in blue.
There are two versions of the Program, the initial version RobotV1.java with limited capabilities and the final version Robot.java. The final version allows robotic navigation in all directions and allows the robot to continue its search until it either finds the required room or the maximum number of turns are exceeded, currently set at 30 turns. The final version also provides a Restart option whichshares the RunBest command. The RunBest command displays after, and only after, selecting a mission from the Command pane when, and only when, a path to the room has already been found. Otherwise, the Restart command displays from the Command pane.
1) Start the application program.
2) Select Do Laundry or Do Dinner from the Command panel
The Do Laundry option can be selected from the Enter key.
The Do Dinner option can be selected from the Space bar.
3) The Do Laundry and Do Dinner keys change
to Learn New when selected, to learn a path to the
required room.
The best path is saved to an array in a linked list, Robot Memory, where
linked nodes are referenced by mission names.
4) Select the Learn New to learn a new path for the requested assignment or mission.
5) If the robot was successful in locating
the correct room, then the best path so far to the room required to complete
the requested assignment/mission can be selected from the
Run Best option off the Command pane.
6) Optionally, the robot can
continue to learn new paths, by reselecting the
Learn New option. The best path for the
requested assignment or mission is saved in the robot’s memory. Once
the shortest path to the room is found, then
it will be permanently recorded in the robot’s memory, until the
simulator is restarted.
7) Pertains to version 1:
If the robot finds the wrong room for the mission – for example, the kitchen
when it needs the
washroom – a new screen is displayed to indicate the robot was not successful, and to inform
users to try again.
8) Pertains to version 1: If the
robot finds the wrong room, select a new assignment
or mission from the Command pane,
and then select the
Learn New option again.
9) To run an assignment for the first time, select the new assignment and then select the Lean New option.
1) No known issues.
1) Fixes have been made to the initial version, RobotV1, to correct a defect running the shortest path. I was not aware of this defect prior to creating the final version. The defect has been removed, and the problem corrected.
2) The final version allows robotic navigation in all directions and allows the robot to continue its search until it either finds the required room or the maximum number of turns are exceeded, currently set at 30 turns. The final version also provides a Restart option which shares the RunBest command. The RunBest command displays after, and only after, selecting a mission from the Command pane when, and only when, a path to the room has already been found. Otherwise, the Restart command displays from the Command pane.
1) Set the background of the robot to a transparent color.
2) Have the robot learn the path to the room for the required mission from any room, and then store this data to memory, so it can be accessed once the robot enters a room having the required information stored in memory. This option would assist learning the shortest path, if it has not already been discovered.
3) Use Prolog for the data structure, instead of the linked list in Java which it currently uses.
Wang, Pei. "Robot and Agent." <http://www.cis.temple.edu/~pwang/203-AI/Lecture/IO-3.htm>
Luger, George, F. "Planning and Robotics." Artificial Intelligence.5th Ed. Harlow, England: Addison-Wesley 2005.
Giancoli, Douglas, C. "Light: Geometric Optics." Physics. 5th Ed. Upper Saddle River: Prentice Hall 1998.
