Transcript Презентация PowerPoint - Knowledge Genesis

«Knowledge Genesis»
Software Engineering Company
Multi-Agent Technologies for
Complex Problem Solving
Dr. Petr Skobelev
SEC «Knowledge Genesis» (Samara, Russia)
Founder and Chairman of Board of Directors
http://www.kg.ru
[email protected]
SEC «Magenta Technology» (London, UK)
Со-Founder and member of Board of Directors
http://www.magenta-technology.com
[email protected]
Agenda
• Short acquaintance with the Samara region and the
company
•Why multi-agent technologies?
•Examples of successful projects based on multi-agent
technologies
 Samara Region е-government
 Adaptive real-time schedulers
 Text Understanding
 Data mining
•Conclusion
Samara, Russia











Region of 3.3 million people
Located on the bank of Volga river
City of 1.2 million people
Second capital of USSR during WWII
National airspace industry centre
High Tech Defence industry centre
Centre of National logistic Network
 Railways, air and automobile hub
Educational centre for Volga region
 13 Higher Education Institutions
 72 Academic Institutions
Traditions and high prestige of engineering
professions
Mature and highly developed IT- market
Innovations actively supported by the
Samara Regional Administration
SEC «Knowledge Genesis» (Russia)
• Established in 1997 in Samara
• Originally from airspace industry and Russian Academy of Sciences
• Unique competences in Multi-agent systems and Semantic web
• Advanced business & technology vision for solving complex
problems
• Innovative technologies for distributed decision making support
• More than 100 J2EE and .net programmers and engineers
• Expertise in large-scale systems, web-applications, data bases, etс.
• Affiliated company – Magenta Technology (UK) – 2000
• Own development platform
• International Network of Partners
• Strong connections with Universities and Research Institutes
• Flexibility and individual approach to each Customer
About the Company






Founded in 2000 together with EU
Investment Funds
Solve complex real-world problems using
Multi-Agent Systems
Main directions of work:
 Systems for scheduling of oil tankers,
trucks, taxis, factories, etc
 Internet marketing and advertising
 Operational platforms design
Reducing costs & increasing customer
business performance
Clients in USA & UK
 Headquartered in London
 Development Centre in Samara
Strong connections with Universities in
Russia, UK and USA
Development center in Samara, Russia
Why Multi-Agent Technology?








One of the new critical software technologies
Capable of applying Fundamental Principles of Self-Organization and
Evolution
Provide smart, flexible and pro-active software solutions
Based on negotiations, conflicts solving and finding trade-offs
“Crack” previously unsolvable problems
Address limitations in existing technology solutions
Allow representing real-world objects and processes
Solve problems the way people do
Developments, Products & Technologies
• e-Government Systems for Welfare and
Healthcare
• Real time GPS-based Adaptive
Schedulers
• Enterprise Decision Making Support
Systems
• Internet Portals
• Web-based Data Mining
and Text Understanding Systems
• Multimedia, 3D-Graphics and Animation
• Geographic information systems
• e-Learning Systems
Multi-Agent e-Government system for Social
sphere of the Samara region
Designed for providing targeted
state services based on social
cards of citizens
Multi-Agent e-Government system for Social
sphere of the Samara region
• Provides targeted state services
• Based on social passports and smart cards of citizens
• Knowledge Base contains more than 500 social laws (federal,
regional and municipal): rules applicable to citizen data
• Personalized agent attached to each citizen
• Available via the Internet and “Internet-Kiosks”
Knowledge Bases of Social Legislation
Multi-agent e-government system for social sphere of the Samara
region is based on Knowledge bases of social legislation (in the
form of semantic networks) containing:
 Integrated knowledge bases of federal, regional and
municipal laws;
 Regulations for state services provision.
Databases vs Knowledge Bases
Knowledge
Base
Database
№
1
Name
Ivanov Ivan
Ivanovich
Year
Post Address
1934
Samara, Sadovaya
Street 34-7
Human
Law
Category
Benefit
Rules
Source of
financing
Organization
address
Databases vs Knowledge Bases
Databases
• Rigid database scheme, new
attributes require new
programming
•Data organized as a sequential
indexed arrays
•Database elements are data only
•Queries are pre-defined and
programmed in advance
• Effective storage for simple
homogeneous sets of data only
(for example, years of birth, post
addresses)
Knowledge
bases
• Extensible «glossary of terms» for
description of new laws and citizen
characteristics
• Data represented as a semantic
network
•Concepts/relationships and rules can
be included into network
•Queries should discover facts and
can be carried out using complex
logical reasoning
• Effective storage for diverse data on
citizens (social, medical and other
information)
Personal data are distributed
Databases
Social Insurance
Databases
Pensions
Databases
Healthcare and
Social Support
Social Cards and their extensions
A Social card is a way of providing services to
each citizen on individual basis
Main features:
1. Identification of Citizen
4. Public Transport discounts
2. Social Benefits
5. Loyalty programs
3. Healthcare
6. Payments
Samara region: The results of the First
stage of Deployment
• 37 towns & villages
•260 Internet kiosks
• Knowledge Base contains 534 laws
and regulation acts
- 278 Federal
- 164 Regional
- 92 Municipal
• Works for social care, healthcare,
electricity and water supply, education
and other social domains
• Social benefits for veterans, disabled
people and many other categories of
citizen
• 120000 social cards
• 50 Social Manager workstations
• 37 Knowledge Engineer workstations
• 6 Chief Executive Authority
workstations
Multi-Agent Scheduling
Technological Platform
•
•
•
•
•
•
• Based on Semantic web technology
• Ontology to capture Enterprise Knowledge
and keep it separately from source code
• Decision Making Logic based on Ontology
• Able to Learn (Using Pattern Discovery
module)
Swarm-based approach (vs mobile agents)
Supports Complex networks
Influenced by real market mechanisms
Adaptive, Real time and Event-driven
Agents are Pro-Active
Provide Emergent Intelligence
Multi-Agent
Technologies
Ontologies
Enterprise
Platform
•
•
•
•
•
Java-based
J2EE architecture
Scalable/Robust
Strong visualizations
Desk-Top & Web-Interface
MAT Solutions based on Virtual Market of
Demands and Resources
Virtual Market
S
Demand-Supply
Match
S
D
D
S
S
D
S
D
D
S
Demand
Agent
S
D
D
Match
Contract
S
S
D
D
S
D
Demand and Supply Matching
(orders and resources in logistics, words and semantics
in text understanding, data and clusters in Clustering)
S
Supply
Agent
MAT Solutions for Real Time Logistics
Designed for resource
scheduling in real-time
mode, supply chains
optimization,
business performance
enhancement
MAT Solutions for Real Time Logistics
 Truck
Scheduling
 Ocean tankers Scheduling
 Taxi Scheduling
 Courier Scheduling
 Car Rental Optimization
 Factory Scheduling
 Supply Chain Optimization
Example: European transportation Network
VOL: 10 PALLETS
SLA: 5 DAYS
VOL: 10 PALLETS
SLA: 10 DAYS
VOL: 5 PALLETS
SLA: 2 DAYS
20%
60%
20%
VOL: 10 PALLETS
SLA: 10 DAYS
120%
80%
20%
60%
VOL: 5 PALLETS
SLA: 8 DAYS
20%
60%
100%
60%
40%
It is important
to of
behaving
able toa assess
Imagine
the power
single
alternate
routes,
to meet
services
system
that
can
plan
This
order
has
a automatically
shortest
journey
levels
and
minimum
cost.
and re-plan aroute…
network like this, as
events
such
orders
…but
theoccur,
capacity
is as
notnew
available
being added
orof
resource
on one
the legs.availability
changes.
Transport Logistics Network Complexity













Real-time scheduling with shrinking time windows
Large & complex networks (> 1000 orders per day, > 100 locations, > 50
vessels )
Less-than-Truck loads requiring effective consolidation
Need to find backhaul opportunities
Intensive use of crossdocking operations
Trailer swaps
Numerous constraints on products, locations, dock doors, vehicles: types,
availability, compatibility
Individual Service Level agreements with major clients
Own and third-party fleet
Fixed and flexible schedules
Dependent schedules (trailers, drivers, dock doors)
Real time economy
Activity Based Cost Model, etc
Most of large & complex networks are
still scheduled manually!
Architecture of Multi-Agent Platform
Current Situation
and Ongoing Plan
Re-Design of
Network
Pattern
Discovery
Patterns
and Ongoing
Forecast
Evolutional
Design
Resulting Plan and KPI
Adaptive
Scheduler
Events Flow
Network (Scene)
Ontology
Editor
Ontology
Domain Knowledge
Network Designer
Simulator
Modeling Data
Modeling Plan
and KPI
Multi-agent Scheduler: Screen Example
Logic of Multi-Agent Scheduling
•Consider a schedule
•New order arrives
08:00
•Preview
•New order ‘wakes up’ Truck 3
agent and starts negotiations
with him
•Truck 3 evaluates the options to
take New order
•Truck 3 ‘wakes up’ Order 3
agent and asks it to shift to the
left
•Order 3 analyzes the proposal
and rejects it
•Truck 3 asks New order if it can
shift to the right
•Truck 3 decides to drop Order 3
and take a New order
•Order 3 starts looking for a new
allocation and finally allocates
on Truck 1 by shifting Order 1
12.00
Time
Truck 1
Which truck is best
for me? 16:00
New order
Заказ 1
I can’t shift
Truck 2
No Can you shift to
the right?
Order 2
Order 3
Can you shift
to the left?
Truck 3
Will you take me?
I can take new order if I:
•Shift Order 3 to the left
•Shift New order to the right
•Drop Order 3
20:00
Logic of Multi-Agent Routing
A
X
Cross dock 1
Z
B
C
Cross dock 2
Y
Consider logistic network of a company
1.Order1 goes from Point C to Point Z
2.Order2 goes from Point B to Point X
3. Заказ3 appears, and goes from Point A to Point Z
4.Order3 decides to go to B and then travel with Order 2 via cross-dock1
5.Order4 appears and goes from Point A to Point Y
6.Order3 decides to travel the first leg with Order 4 and the second leg with Order 1 via crossdock 2, to avoid going alone from A to B
Case Study: UK Logistics Operator
Network Characteristics:


4500 orders per day
Order profile with high complexity










Many consolidations should be found
Few Full Truck Load orders
Few orders can be given away to TPC
Majority of orders require complex planning – the
price of a mistake is high
600 locations
Large number of small orders
3 cross docks
9 trailer swap locations
140 own fleet trucks, various types
20 third party carriers


Carrier availability time
Different pricing schemes
Problems to be Solved:
Location availability windows
Backhaul
Consolidation
Vehicle capacity
Constraint stressing
Planning in continuous mode
Dynamic routing
Cross-docking
Handling driver shifts
Key Problem: Real-time planning
in a highly complex network with
X-Docks and Dynamical Routing
Summary of Benefits (Before / After)
BEFORE IMPLEMENTATION
AFTER IMPLEMENTATION
Two operators worked for a day
to make a schedule for 200 instructions
8 minutes to schedule 200 transportation
instructions
Planning day 1 for day 3: no chance to
Support backhauls and consolidations
in real time
Planning day 1 for day 2 and even day 1
for day 1
No software for schedule 4000 orders
With X-Docks and Drivers
(manual procedure only)
4 hours to plan orders 4000 orders via
X-Docks and ability to add new orders
incrementally (a few seconds for a order)
Knowledge was hard to share, it was
“spread” among different experts
Capture best practice and domain
knowledge in ontology. New
knowledge can be inserted quickly.
Hard to consider various criteria
quickly and choose the best possible
option
Choosing the best route from the point
of view of consolidation or other criteria
Key Customers






Avis (UK): Leading car rental provider
 Innovative dynamic scheduling system for downtown market reducing
car assets required and improving service levels
Addison Lee (UK): largest private hire car firm in London
 delivering core operational systems and dynamic scheduling
Tankers International (UK): Manage a large oil tanker fleet
 development of dynamic scheduling software for shipping fleet
One Network (USA): logistics software provider
 providing development services to implement new core, scheduling
and visual features/components for their platform
GIST (UK): supply chain specialist
 real-time scheduling software tool for increased fleet utilisation and
reduced transportation costs
Enfora (USA) : major manufacturer of handheld devices
 development of a wide range of software modules and market
partnership for a dynamic scheduling web service
Move forward with Multi-Agent Systems
That Was Then
Batch
Optimizers
Rules Engines
Constraints
Visualize
This is Now
Real-time
Manage Trade-offs
Decision-Making Logic
Cost/value equation
Learn, Simulate
and Forecast
Adaptive Factory Scheduler
Main features include:






Creation of production plans;
Planning of production equipment, operations,
resources based on ontology;
Adaptive rescheduling in response to unexpected events
(equipment failures, operation delays, etc.);
Visualization of current production plan;
Description and updating system knowledge through
the ontology;
Semiautomatic editing of production plans. For
example, a user may change the initial plan for any
machine or equipment or add new production tasks,
change or cancel some of previous tasks and
operations, etc.
Adaptive Factory Scheduler
User plans production processes by
assigning resources for their fulfillment
(machines, equipment etc.)
Results of scheduling are presented in
Gantt chart form showing the level and the
intensity of resources utilization in the
course of production plan fulfillment
Adaptive Factory Scheduler
…and visualize factory
ontology with adjustable
detailing level
Data («knowledge») about resources
are entered and stored in ontology.
Adaptive Factory Scheduler allows
operating with ontology data,
updating, modifying and deleting
them…
Factory ontology example
• Actively developing in Semantic Web
for Internet pages semantic
description
• Factory Ontology contains
description of basic domain objects
and relationships between them.
• Ontology allows to represent
knowledges of certain domain
separately from program code
In order to manufacture a driving
mirror it is necessary to make a
form, to cut glass, to paste glass to
a substrate, etc.
For this purpose we need the
following materials: a plate, glass,
substrate, glue, and other raw
materials.
Each operation should be carried
out by skilled worker…
• Ontologies usage allows to build
flexible and scalable applications
easily adopted to any business by
means of changing «system
knowledge» by demand.
• Ontologies can be successfully
applied for decision support,
learning, knowledge integration and
other areas.
Adaptive Factory Scheduler
Achieved results:







Production planning on the basis of real resources characteristics (equipment, machines,
workers), their availability at various time periods and information about changes
Combination of the planning stage with plan execution monitoring, flexible rescheduling
Monitoring of technology and production plans
More efficient strategic and tactical planning in response to maximum requirements in the
condition of uncertainty, resources distribution conflicts and high risks
Enhanced visualization capabilities (Gantt charts, semantic networks)
Higher adaptability and configuration capabilities
Execution of orders just in time through flexible planning in the real time mode
Benefits of MAS for Real Time Logistics









Solves “unsolvable” problems in complex logistic networks
Supports event-driven, continuous planning in real time with intelligent
reactions to unexpected events
Fast reaction: reactive and pro-active changes of parts of the schedule
without changing the whole schedule
Provides smart decision support and sophisticated user interaction
 Reacts on events and constantly generates new options proactively
 Provides individual & detailed cost calculations per order / resource
 Makes trade-offs to balance different criteria (cost, profits and service levels)
 Provides ability to override constraints
 Supports collaborative team work with users
 Provides integration of scheduling processes across the company
 Makes decision making visual
Knowledge-based: Uses domain- and company-specific knowledge to
produce feasible schedules and reduce dependency on key individuals
Customizable and configurable
Platform for supporting business growth and performance increase
Reduces cost & time, improve service, lower risks and penalties
Supports «what-if» games for business optimization
KEIS: Intellectual data mining
Designed to discover patterns, hidden
dependencies and business-critical
knowledge in the databases, texts and other
information resources
KEIS: Intellectual data mining
Problems of traditional data analysis




Traditionally, data analysis is carried out by human.
However, human cannot find more than two-three dependencies
even in small data files, and at the same time mathematical
statistics operates with averaged parameters and cannot help in
practical recommendation preparation.
In contrast with the traditional methods of data analysis, KEIS
discovers hidden rules and dependencies automatically.
KEIS is designed for analysis of data extracted from different
sources and presented in different formats.
KEIS: Intellectual data mining
Cluster analysis basics
Clustering is one of the basic approaches used to
discover hidden patterns in the huge information
files
Cluster analysis allows to find previously unknown
dependencies in data. These dependencies are
hardly discovered using other approaches.
Clustering divides data into groups (clusters) where
elements inside one group have more «similarity»
among themselves than with elements in neighbor
clusters
Clustering Technology
Databases
Data transformation to possible
input data formats
Файлы формата txt.
(Блокнот)
Файлы формата mdb.
(Microsoft Access)
Файлы формата xls.
(Microsoft Excel)
Cluster analysis
Data loading…
Discovery of clusters
Cluster4
Cluster 1
Data processing
Cluster 3
Cluster 2
Stages of KEIS data processing
Basic stages
1.
2.
3.
4.
5.
6.
Data loading
Data processing
Analysis by attributes
Cluster analysis
Cluster content analysis
Automatic generation of semantic rules
Stage 1: Data loading
System GUI
Pre-processing
Data file opening
On the first stage data loading
and pre-processing are
executed
Stage 2: Data processing
Initializing clustering process
On this stage clustering of full data set
by selected attributes has to be
executed
Information about
discovered clusters
then is shown in the
table
Stage 3: Data analysis by attributes
Detailed research of cluster
parameters using categories of
selected attribute is carried out on this
stage
Select an attribute
Stage 4: Cluster Analysis
All clusters discovered in
loaded data are presented
in pie chart.
This stage is a visualization stage.
Segments of pie chart correspond with
discovered clusters, and its size allows to
evaluate number of records in certain
cluster
Content of each cluster can
be analyzed in details in the
system…
…or exported for review
and further processing to
Microsoft Excel.
Stage 5: Analysis of cluster’s content
At this stage, detailed
information about all
categorial attributes for
the selected cluster can
be presented.
Each attribute is shown
at the diagram using
colored area.
Selected cluster
visualization.
content
Height of this area allows
to evaluate total number
of records with certain
attribute, in selected
cluster.
Stage 6: Semantic rules generation
At this stage system allows to formulate
Automatically
generated
rules
are shown by
correspondences
between
different
the
systemin a logical form «if…then».
attributes
Selection of logical scheme
(conditionconclusion) by
the user
generating…
If user has a car, then he often travels
with:1.Family; 2.Partners; 3.Friends
KEIS: Intellectual data mining
Basic advantages of KEIS







High performance
High reliability of analysis results
Flexible cauterization parameters settings
Possibility to process big information files contains
hundreds of thousands of records where each record can
has hundreds of attributes
Support of different formats of input data (txt/xls/mdb)
Possibility of clustering using many parameters
Possibility to handle both quantitative and nonquantitative parameters
KEIS: Case study. Social sphere

Data analysis related to recipients of social support in Kinel
town allowed to determine all groups of recipients and their
basic characteristics
Discovered clusters
Cluster diagram
KEIS: Case study. Car insurance

Insurance company provides car insurance service and has staff experts who on
the basis of several criteria (official requirements and personal expertise) makes
decisions of business conditions for certain client. Guessed decisions include
providing of insurance or rejecting of service, tariffs, potential legal costs, etc.

Cluster analysis allows «to discover» hidden dependencies between client
characteristics and insurance accident risks by special client’s data processing.
Discovered clusters
Cluster analysis allowed to find out most secure and insecure
segments of clients
KEIS: Case study. Mobile operator

Mobile company database analysis allows to discover main groups of
clients and their preferences
Main groups of clients.
Different services usage statistics
Cluster №9 corresponds to the largest segment of
clients (6141 records – 45%)
Local traffic two times more than average, roaming
is tree times less than average, Long distance calls
at average level, additional services at average level.
I. е. predominantly local calls.
Most likely, usual local residents
Text Understanding with generation of
semantic network
Intellectual text processing and analysis implies understanding its
semantics.
Text semantics can be presented in the form of a semantic network
(scene) - the information structure reflecting concepts, objects,
subjects mentioned in the text, and relations between them.
Domain ontologies are used in order to create scenes.
Instances:
• Molecular biology article’s abstracts understanding
• Insurance company contracts processing
• Semantic information search
• Perspective: Semantic-based terrorists SMS or e-mail messages (or
even phone calls) recognition
Example: Generation of semantic descriptor for
molecular biology article excerpt
Analysis of the first sentence
Analysis
Analysisofofthe
thesecond
third sentence
sentence
Two
pUC-derived vectors
Two
Two pUC-derived
pUC-derived vectors
vectors
containing
the
Модуль
построения
containing
containing the
the
promoterless
семантических
promoterless
promoterless
xylE
gene (encoding
дескрипторов
xylE
xylE gene
gene (encoding
(encoding
catechol
2,3-dioxygenase)
ориентирован
на анализ
catechol
catechol 2,3-dioxygenase)
2,3-dioxygenase)
of
реферата и создание на
of
of
Pseudomonas
putida mt-2
основе онтологии
Pseudomonas
Pseudomonas putida
putida mt-2
mt-2
were
constructed.
The
t(o)
предметной
области
were
were constructed.
constructed. The
The t(o)
t(o)
transcriptional
terminator
семантического
transcriptional
terminator
transcriptional terminator
of
phage lambda
was
дескриптора,
однозначно
of
of phage
phage lambda
lambda was
was
placed
описывающего
данный
placed
placed
downstream
from the
stop
реферат. Дескриптор
для
downstream
downstream from
from the
the stop
stop
codon
of xylE.
The new
каждого
реферата
codon
codon of
of xylE.
xylE. The
The new
new
vectors,
pXT1
and
pXT2,
строится
единожды,
и
vectors,
pXT1
and
pXT2,
vectors, pXT1 and pXT2,
contain
xylE and
the t(o)
далее работа
contain
contain xylE
xylE and
and the
the t(o)
t(o)
terminator
within
a
cloning
осуществляется
со
terminator
terminator within
within aa cloning
cloning
cassette
which
can
be
сформированной
базой
cassette
cassette which
which can
can be
be
excised
with
several
дескрипторов.
excised
excised with
with several
several
endonucleases.
endonucleases.
endonucleases.
System Architecture
Patterns
Library
Signal of pattern detection
Parents-Children
MAS for
pattern
detection
Goods
…
Small business
Domain Ontology
SMSmessages,
е-mails, etc.
MAS for scene
clustering
MAS for Text
Understanding
Language
Options
Clusters
Scene
Scenes
Archive
Ontology extension requests
MAS for
language
queries
Typical
Queries
Where Vasya
waslast
week?
Semantic network generated in course of text
analysis
Conclusion
1. Knowledge Genesis develops innovative multi-agent systems
applicable to complex problems solving in various domains
2. First experience of multi-agent systems development for egovernment, adaptive planners, text understanding, clustering
demonstrates high efficiency and existence of good perspectives
of the approach on world market
3. Currently Knowledge Genesis is working on new generation of the
high-performance multi-agent systems functioning on distributed
network of servers and allowing learning by experience
4. We will be happy to have new possibilities for further development
and application of our technologies in different domains to solve
complex problems
THANK YOU!
Russia, Samara, 443001,
Sadovaya street 221
Tel/fax: 007-846-3322101
www.kg.ru
[email protected]