Course:CPSC522/Hierarchical Control
Hierarchical Control
Hierarchical Control System is a control system in which all the inter-related sub-systems are arranged one over other, as layers, in a hierarchical manner such that each high level layer receives percepts from and sends command to the layer below it and each sub-system follows similar hierarchical structure.
Principal Author: Tanuj Kr Aasawat
Collaborators: Prithu Banerjee, Ritika Jain
Abstract
Most difficult part in today's large scale systems is to keep things simple. In order to achieve simplicity, system is divided into layers/modules, each layer performing some specific functions. This leads to a system which is scalable, maintainable and easy to troubleshoot. This page provides technical overview of Hierarchical Controller used widely and everywhere, not limited to AI world. It describes the architecture of hierarchical controller, advantages it provides and the practical example of its usage by UBC Thunderbots team on building an AI framework for RoboCup Soccer in the Small Size League at RoboCup.
Content
In words of Herbert A. Simon,
By a hierarchic system, or hierarchy, I mean a system that is composed of interrelated subsystems, each of the latter being in turn hierarchic in structure until we reach some lowest level of elementary subsystem. In most systems of nature it is somewhat arbitrary as to where we leave off the partitioning and what subsystems we take as elementary. Physics makes much use of the concept of “elementary particle,” although the particles have a disconcerting tendency not to remain elementary very long . . .
Empirically a large proportion of the complex systems we observe in nature exhibit hierarchic structure. On theoretical grounds we would expect complex systems to be hierarchies in a world in which complexity had to evolve from simplicity.
– Herbert A. Simon, 1996
The principle of hierarchy is common in almost every real world systems like ecosystems, organizational and political systems as well as human cognitive system. Hierarchical control can be interpreted as a technique to decompose complex problems into smaller sub-problems and then reassembling their solutions into a working hierarchical structure. Complexity is a major concern in many large control problems, and it is common engineering knowledge that suitable decomposition techniques form a necessary ingredient for any systematic treatment of large complex control problems. Hierarchical approaches, where several control layers interact, are a particularly efficient way of problem decomposition as they provide an extremely intuitive control architecture. Hierarchical structure is particularly essential in large scale systems, systems of very high complexity, where complexity is typically reduced/managed by imposing a hierarchical structure on the system architecture.
Background
Here we will give the basic information about agents, environment and other terminologies we are going to use. From high level of perspective, an AI is comprised of one or more agents and their environment. An agent is anything that can perceive its environment through sensors and acts upon that environment through effectors/actuators. Examples: a person, a lion, a robot or a computer program that buys and sells. Environment of an agent is the world in which it acts or with which it interacts. An agent receives information/stimuli from its environment through its sensors and its actions depend on the information it receives from its sensors. Examples of sensors are: cameras, infrared sensors, keyboard, microphone, bar code readers etc. An agent acts in its environment through its effectors/actuators. Actions could be kicking a ball, steering, moving forward/backward/at a particular location etc. These sensors and actuators makes up the body of the agent. The other part of an agent is called as controller, brain of the agent, which receives percepts from the body and sends commands to the body. Commands are either low-level or high-level. Low level commands are generally quantitative based, like setting speed of the robot to a particular value. High level commands are generally qualitative, like go near the ball or cover the goal keeper, travel straight or take a turn etc.
Hierarchical Agent System
One way of building an agent is putting sensors and actuators in body and having a controller which acts as a reasoning engine. The problem with this approach is that it's very slow, it's not scalable, reasoning engine would become slow for complex and high-level goals. These deficiencies reinforces that this kind of architecture shouldn't be used in real time systems. The better solution is to have hierarchy of controllers arranged in layers, as depicted in Figure 1, where each higher layer sees the layer below it as a virtual body from which it gets percepts as input and to which it sends commands. This helps the lower-level layer to run faster and react to those aspects of the environment where it needs to react quickly and also to deliver a simpler/abstract view of the environment to the higher-level layers.
Input
There are three types of inputs to each layer every time. They are:
1. Previous state: values of features coming from the belief state, also referred as previous values of the features.
2. Low-level percepts: percepts from the layer below in hierarchy.
3. High-level commands: commands from the layer above in the hierarchy.
Output
There are three types of outputs from each layer every time. They are:
1. Next state: New values for the belief-state features.
2. High-level percepts: refined percepts for the layer above.
3. Low-level commands: commands for the layer below.
High-level reasoning is carried out in higher layers and is mainly qualitative and uses discrete values. Low-level reasoning is carried out in lower layers and is mainly quantitative and uses continuous values.
What's the need of Qualitative representation?
Well, while designing an agent we don't exactly know all the minute details of real world interaction of our agent with the environment. For example, while designing a soccer robot, it's possible that we don't know the exact/optimal value of steering angle if there is any opposition's robot in front of it. And the lower layer responsible for steering can handle such cases while interacting with the environment. This helps in having a simple design and makes lower layers act quickly for such cases. Furthermore, an agent needs to perform qualitative reasoning before going into quantitative reasoning and some times there might be a case that quantitative reasoning is not required at all, like if the weight of the parcel robot wants to deliver is within permissible limit or not, and afterwards only, if required, it will check for parcel's weight category - light/medium/heavy weight. So, in short, an agent does not always need to perform quantitative reasoning but it has to always perform qualitative reasoning.
Advantages and challenges
Designing the AI in a structure of hierarchy of different levels of abstraction offers many advantages. Each level of the hierarchy can be designed to focus on accomplishing a particular role with the assumption that the other layers that it interacts with accomplish their roles as well. For example, the layer in charge of controlling the direction of a robot can assign lower level behaviors without knowledge of how the behaviors are actually implemented. This hierarchy offers clear advantage by modularizing the different levels of abstraction. Implementing these independent modules is much simpler as each module represents a small part of the global problem. Another advantage of using a hierarchy is that from a software engineering perspective it makes the system more extensible, scalable and easier to understand. For example, instead of having to completely rewrite the code in order to create a new strategy, only a single layer at the top of the hierarchy would need to be modified. Information about other control system is available here.
One of the main challenges of hierarchical systems is the extraction of a hierarchy of models at various levels of abstraction which are compatible with the functionality and the objectives of each layer.
Practical Example of a Hierarchical Controller
This section describes the design of hierarchical controller of an Artificial Intelligence (AI) framework made by a team of UBC Thunderbots which were aimed to compete in the Small Size League at the RoboCup soccer competition.
Background
Robotic soccer was first proposed by Alan Mackworth in 1993 as a testbed for research. RoboCup soccer provides an environment for testing AI in which many different techniques can be competed against each other in a structured competition. The official goal of the RoboCup competition is "by the year 2050, develop a team of fully autonomous humanoid robots that can win against the human world soccer champion team." The Small Size League is one of the variety of competitions hosted by RoboCup. The Small Size League consists of robots no larger than 18 cm in diameter. There are six robots in a team playing on a field slightly bigger than a ping-pong table. The soccer ball is the size of a golf ball. A match consists of two 10-minute halves.
Figure 2 illustrates the setup for the Small Size League. There is an overhead camera which captures video of the game and sends it to a computer. The computer then analyzes the images and sends out wireless signals to control the robots. The robots have unique colored markers to allow them to be visually identified. More details on the rules of the game and constraints on robot design are available on the RoboCup website.
Design
Here, a central computer does the processing for all of the robots as it offers a significant advantage over autonomous robots because it eliminates the need for communication and negotiation between independent agents. For example, if each robot was acting independently, in order to come up with an effective team strategy the robots would need to communicate with each other and decide upon a single plan. The independent robots would each have a different view of the environment so they might have different opinions on what the best team strategy might be. Since the central computer has access to all of the information available it can determine the best strategy and issue commands to the robots. Besides the camera feed, another input that the central computer receives is data from a program called the RefereeBox. The RefereeBox is controlled by the human referee and communicates game information to the central computer. This game information contains data such as the current score and the current type of game play (such as penalty kick, kickoff, etc.).
Using principles from the field of software engineering such as the application of design patterns and object oriented programming, a high level system was designed. So, instead of basing the system on a single AI technique, the problem was split up into smaller sub problems. This allowed the application of various AI algorithms on the simpler sub problems.
Figure 3 illustrates the hierarchy used for this AI system. The AI has been split into five modules/layers:
1. Central Analyzing Unit: Receives and analyzes data from the IR module. This layer acts as an interface to the AI and controls the execution of the other layers.
2. Decision Unit: Receives inputs from the RefereeBox and sets the global strategy type. The global strategy types can be: Do nothing, Get in starting positions, Ball is in play, Direct free kick, Indirect free kick, Penalty kick, Throw in, Goal kick, Corner kick, Victory dance.
3. Central Strategy Unit: Based on the global strategy type, a behavior is assigned to each robot. Behaviors assigned to robots include: Stop, Pass ball to another player, Receive pass from another layer, Shoot ball, Chase ball, Go to a location on the field, Be the goalie.
4. Local Strategy Unit: Based on the robot's behavior, lower level commands are sent to the Robot Controller. Low level commands include: Direction to move, Direction to face, Whether or not to dribble the ball, Whether or not to kick the ball.
5. Robot Controller: Translates and transmits low level commands into wireless signals.
There are hierarchies within the layers of the AI module as well. Within the Local Strategy Unit some behaviors are lower level than other behaviors. Higher level behaviors can be implemented using a combination of lower level behaviors. For example, to implement the shoot ball behavior, the chase ball behavior can be used if the robot does not have control of the ball. The chase ball behavior in turn uses the move behavior in order to get closer to the ball.
Based on the global strategy type, the central analyzing unit can execute a particular type of strategy. These strategies are used to assign behaviors to the robots. For example, if the global strategy type is "get in starting positions" then each robot will be assigned a move behavior to the location of its starting position.
Annotated Bibliography
David Poole & Alan Mackworth, "Artificial Intelligence: Foundations of Computational Agents", Chapter 2.3
UBC Thunderbots
Hierarchical Controller for Robotic Soccer
RoboCup Small Size League
RoboCup Wiki
RoboCup 2016 http://www.robocup2016.org/en/
UBC Thunderbots Youtube Channel
http://www.mpi-magdeburg.mpg.de/95036/Hierarchical-Control-Theory