sample prolog programs

http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2.html

search algorithms in prologs

http://bkraabel.free.fr/pages/prolog.html

breadth first in prolog

 

PROLOG

%%%%%%% Breadth first search algorithm%%%%%%%%
%%%
%%% This is one of the example programs from the textbook:
%%%
%%% Artificial Intelligence: 
%%% Structures and strategies for complex problem solving
%%%
%%% by George F. Luger and William A. Stubblefield
%%% 
%%% Corrections by Christopher E. Davis (chris2d@cs.unm.edu)
%%%
%%% These programs are copyrighted by Benjamin/Cummings Publishers.
%%%
%%% We offer them for use, free of charge, for educational purposes only.
%%%
%%% Disclaimer: These programs are provided with no warranty whatsoever as to
%%% their correctness, reliability, or any other property.  We have written 
%%% them for specific educational purposes, and have made no effort
%%% to produce commercial quality computer programs.  Please do not expect 
%%% more of them then we have intended.
%%%
%%% This code has been tested with SWI-Prolog (Multi-threaded, Version 5.2.13)
%%% and appears to function as intended.

    
state_record(State, Parent, [State, Parent]).

go(Start, Goal) :- 
    empty_queue(Empty_open),
    state_record(Start, nil, State),
    add_to_queue(State, Empty_open, Open),
    empty_set(Closed),
    path(Open, Closed, Goal).

path(Open,_,_) :- empty_queue(Open),
                  write('graph searched, no solution found').
    
path(Open, Closed, Goal) :- 
    remove_from_queue(Next_record, Open, _),
    state_record(State, _, Next_record),
    State = Goal,
    write('Solution path is: '), nl,
    printsolution(Next_record, Closed).
    
path(Open, Closed, Goal) :- 
    remove_from_queue(Next_record, Open, Rest_of_open),
    (bagof(Child, moves(Next_record, Open, Closed, Child), Children);Children = []),
    add_list_to_queue(Children, Rest_of_open, New_open), 
    add_to_set(Next_record, Closed, New_closed),
    path(New_open, New_closed, Goal),!.

moves(State_record, Open, Closed, Child_record) :-
    state_record(State, _, State_record),
    mov(State, Next),
    % not (unsafe(Next)),
    state_record(Next, _, Test),
    not(member_queue(Test, Open)),
    not(member_set(Test, Closed)),
    state_record(Next, State, Child_record).

printsolution(State_record, _):- 
    state_record(State,nil, State_record),
    write(State), nl.
printsolution(State_record, Closed) :-
    state_record(State, Parent, State_record),
    state_record(Parent, _, Parent_record),
    member(Parent_record, Closed),
    printsolution(Parent_record, Closed),
    write(State), nl.
        
add_list_to_queue([], Queue, Queue).
add_list_to_queue([H|T], Queue, New_queue) :-
    add_to_queue(H, Queue, Temp_queue),
    add_list_to_queue(T, Temp_queue, New_queue).


  

http://www.cs.unm.edu/~luger/ai-final/code/PROLOG.breadth.html

Installing SWI-Prolog Editor

http://lakk.bildung.hessen.de/netzwerk/faecher/informatik/swiprolog/indexe.html

intro to logic

http://veritasdomain.wordpress.com/2007/03/30/lectures-on-introduction-to-logic-philosophy/

http://www.slideshare.net/gracia2k3/logic-ppt

Prolog - Tutorials

http://www.swi-prolog.org/

 http://www.gprolog.org/

http://en.wikibooks.org/wiki/Prolog

http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/

https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/intro.html

Problem Solving in Prolog

Reference: Bratko chapter 12

Aim:

To illustrate search in AI using a fairly well-known example problem. We also briefly introduce a number of different methods for exploring a state space (or any other graph to be searched).

Keywords: breadth first search, depth first search, edge in a graph, goal state, graph, directed acyclic graphs, trees, binary trees, adjacency matrices, graph search algorithms, initial state, node, operator, state, initial state, goal state, path, search, vertex

Plan:

states, operators and searching representing state spaces using graphs finding a path from A to B in a graph missionaries & cannibals: representing states & operators methods of search: depth-first, breadth-first

Problem solving has traditionally been one of the key areas of concern for Artificial Intelligence. Below, we present a common problem and demonstrate a simple solution.

Missionaries and Cannibals

• There are three missionaries and three cannibals on the left bank of a river.
• They wish to cross over to the right bank using a boat that can only carry two at a time.
• The number of cannibals on either bank must never exceed the number of missionaries on the same bank, otherwise the missionaries will become the cannibals' dinner!
• Plan a sequence of crossings that will take everyone safely accross.

This kind of problem is often solved by a graph search method. We represent the problem as a set of

states

which are snapshots of the world and

operators

which transform one state into another

States can be mapped to nodes of a graph and operators are the edges of the graph. Before studying the missionaries and cannibals problem, we look at a simple graph search algorithm in Prolog. the missionaries and cannibals program will have the same basic structure.

Graph Representation

A graph may be represented by a set of edge predicates and a list of vertices.

 edge(1, 5). edge(1, 7).
 edge(2, 1). edge(2, 7).
 edge(3, 1). edge(3, 6).
 edge(4, 3). edge(4, 5).
 edge(5, 8).
 edge(6, 4). edge(6, 5).
 edge(7, 5).
 edge(8, 6). edge(8, 7).

 vertices([1, 2, 3, 4, 5, 6, 7, 8]).

Finding a path

• Write a program to find path from one node to another.
• Must avoid cycles (i.e. going around in circle).
• A template for the clause is:

 path(Start, Finish, Visited, Path).

Start

is the name of the starting node

Finish

is the name of the finishing node

Visited

is the list of nodes already visited.

Path

is the list of nodes on the path, including Start and Finish.

The Path Program

• The search for a path terminates when we have nowhere to go.

 path(Node, Node, _, [Node]).

• A path from Start to Finish starts with a node, X, connected to Start followed by a path from X to Finish.

 path(Start, Finish, Visited, [Start | Path]) :-
  edge(Start, X),
  not(member(X, Visited)),
  path(X, Finish, [X | Visited], Path).

Here is an example of the path algorithm in action.

Representing the state

Now we return to the problem of representing the missionaries anc cannibals problem:

• A state is one "snapshot" in time.
• For this problem, the only information we need to fully characterise the state is:
  • the number of missionaries on the left bank,
  • the number of cannibals on the left bank,
  • the side the boat is on.
  All other information can be deduced from these three items.
• In Prolog, the state can be represented by a 3-arity term,

 state(Missionaries, Cannibals, Side)

Representing the Solution

• The solution consists of a list of moves, e.g.

 [move(1, 1, right), move(2, 0, left)]

• We take this to mean that 1 missionary and 1 cannibal moved to the right bank, then 2 missinaries moved to the left bank.
• Like the graph search problem, we must avoid returning to a state we have visited before.
• The visited list will have the form:

 [MostRecent_State | ListOfPreviousStates]

Overview of Solution

• We follow a simple graph search procedure:
  • Start from an initial state
  • Find a neighbouring state
  • Check that the new state has not been visited before
  • Find a path from the neighbour to the goal.
  The search terminates whe we have found the state:

 state(0, 0, right).

Top-level Prolog Code

% mandc(CurrentState, Visited, Path)

mandc(state(0, 0, right), _, []).
mandc(CurrentState, Visited, [Move | RestOfMoves]) :-
 newstate(CurrentState, NextState),
 not(member(NextState, Visited)),
 make_move(CurrentState, NextState, Move),
 mandc(NextState, [NextState | Visited], RestOfMoves]).

make_move(state(M1, C1, left), state(M2, C2, right), move(M, C, right)) :-
 M is M1 - M2,
 C is C1 - C2.
make_move(state(M1, C1, right), state(M2, C2, left), move(M, C, left)) :-
 M is M2 - M1,
 C is C2 - C1.

Possible Moves

• A move is characterised by the number of missionaries and the number of cannibals taken in the boat at one time.
• Since the boat can carry no more than two people at once, the only possible combinations are:

 carry(2, 0).
 carry(1, 0).
 carry(1, 1).
 carry(0, 1).
 carry(0, 2).

• where carry(M, C) means the boat will carry M missionaries and C cannibals on one trip.

Feasible Moves

• Once we have found a possible move, we have to confirm that it is feasible.
• I.e. it is not feasible to move more missionaries or more cannibals than are present on one bank.
• When the state is state(M1, C1, left) and we try carry(M, C) then

 M <= M1 and C <= C1

• must be true.
• When the state is state(M1, C1, right) and we try carry(M, C) then

 M + M1 <= 3 and C + C1 <= 3

• must be true.

Legal Moves

• Once we have found a feasible move, we must check that is legal.
• I.e. no missionaries must be eaten.

 legal(X, X).
 legal(3, X).
 legal(0, X).

• The only safe combinations are when there are equal numbers of missionaries and cannibals or all the missionaries are on one side.

Generating the next state

newstate(state(M1, C1, left), state(M2, C2, right)) :-
 carry(M, C),
 M <= M1,
 C <= C1,
 M2 is M1 - M,
 C2 is C1 - C,
 legal(M2, C2).
newstate(state(M1, C1, right), state(M2, C2, left)) :-
 carry(M, C),
 M2 is M1 + M,
 C2 is C1 + C,
 M2 <= 3,
 C2 <= 3,
 legal(M2, C2).

The complete code, with instructions for use, is available at http://www.cse.unsw.edu.au/~billw/cs9414/notes/mandc/mandc.pro

Methods of Search

In the preceding example, the state space is explored in an order determined by Prolog. In some situations, it might be necessary to alter that order of search in order to make search more efficient. To see what this might mean, here are two alternative methods of searching a tree. Depth first search begins by diving down as quickly as possible to the leaf nodes of the tree. Traversal can be done by:

• visiting the node first, then its children (pre-order traversal): a b d h e i j c f k g
• visiting the children first, then the node (post-order traversal): h d i j e b k f g c a
• visiting some of the children, then the node, then the other children (in-order traversal) h d b i e j a f k c g

There are many other search methods and variants on search methods. We do not have time to cover these in COMP9414, but you can find out about some of them in the text by Bratko. For example, chapter 12 deals with best-first search.

Summary: Problem Solving and Search in AI

We introduced the concepts of states and operators and gave a graph traversal algorithm that can be used as a problem solving tool. We applied this to solve the "missionaries and cannibals" problem. We also outlined depth-first search, breadth-first search, and alluded to the existence of a range of other search methods.

CRICOS Provider Code No. 00098G
Copyright (C) Bill Wilson, 2002, except where another source is acknowledged.


http://www.cse.unsw.edu.au/~billw/cs9414/notes/mandc/mandc.html

Glossary

• Actuator – something with effects the environment around it
• Agent – anything that can be viewed as perceiving its environment through sensors and acting upon it.
• Agent function – the mathematical way of describing an agents behavior
• Agent program – the agents dedicated programming (implements the agent function)
• Architecture – the layout of the agent
• Artificial intelligence – man-made intelligence.
• Autonomy – how little the agent relies on prior knowledge
• Condition-action rule – a rule which tell the agent how to act given a condition
• Critic – tells the learning element how well the agent is doing
• Deterministic – an environment in which the next state is solely determined by the current state and the action executed by the agent
• Dynamic – the environment can change while the agent is deliberating
• Effecter – something with effects the environment around it
• Environment – the landscape upon which the agent works
• Episodic – the choice of action taken by the agent depends only on the current state
• Goal – what the agent hopes to achieve
• Goal based agent – an agent which chooses an action form a list of actions which helps the agent complete its goals
• Internal state – the previous state of the world held inside the agents’ memory
• Learning – improving techniques through previous experiences
• Learning element – makes improvements to the performance element
• Model based agent – an agent which uses the current state it can see and the internal state to call a condition-action rule.
• Multi-agent – Many agents in one environment communicating together affecting each others decisions
• Observabillity – how much of an agents environment can be seen at any given instant
• Omniscience – when an agent knows an actual outcome of an action and acts accordingly
• Percepts – an agencies perceptual input at any given instant
• Percept sequence – the complete history of everything perceived by the agent
• Performance element – responsible for choosing external actions
• Performance measure – the criterion for an agent’s behavior
• Problem generator – introduces the performance element to new actions
• Rationality – the ideal concept of intelligence.
• Semi-dynamic – if the agents’ performance score can change while the agent is deliberating
• Sensors – something that can describe the environment around it
• Sequential – The current decision chosen by the agent affects all future decisions
• Simple reflex agent – an agent which takes the current situation and acts upon it if it has the correct condition – action rule
• Software agent – an agent whose environment is held in software
• Static – the environment doesn’t change while the agent is deliberating

Applications of agents

Automated driving

This is a goal based, utility based agent. Cameras are used to gain positions of car, the edges of lanes and the position of the goals. The car can speed up, slow down, change lanes, turn, park, pull away…….

                           
In the scenario above car A can do any of the tasks but the ones which stand out as the ones that will have the highest outputs of the utility function are, change lanes or stay behind car B.

Read more about automated driving (external link) »

A.L.I.C.E. – a chat bot

A.L.I.C.E. is an online chat bot, A.L.I.C.E. is a learning reflex agent, and given certain keywords the bot has a predetermined response but if the bot doesn’t know how to reply properly then the bot will ask a question which will help the bot learn how to answer the question in the future. This eventually builds up a large amount of condition-action rules. The more people use A.L.I.C.E. the better A.L.I.C.E. will get at having a fluid conversation.

Try A.L.I.C.E. »

The software agents group

This is a section of MIT that researches into software agents.

MIT Current Projects »
 

IBM - Intelligent Agents Project

IBM are researching agents to help in business

Read more on IBM's project (external link) »

http://www.doc.ic.ac.uk/project/examples/2005/163/g0516334/app.html

Types of Environments

• Deterministic and non-deterministic
  An environment is deterministic if the next state of the environment is solely determined by the current state of the environment and the actions selected by the agents. An inaccessible environment might appear to be non-deterministic since the agent has no way of sensing part of the environment and the result of its actions on it. We have to take into consideration the point of view of the agent when determining whether an environment is deterministic or not since the agent might have limited perception capabilities.

• Episodic and non-episodic
  In an episodic environment, the agent's experience is divided into episodes which consist of a percept sequence and an action. Since episodes are independent of one another and the agent doesn't need to know the effect of its actions.

• Static and dynamic
  An environment is dynamic if it changes while an agent is in the process of responding to a percept sequence. It is static if it does not change while the agent is deciding on an action i.e the agent does not to keep in touch with time. An environment is semidynamic if it does not change with timebut he agent's performace score does.

• Discrete and continuous
  If the number of percepts and actions in the environment is limited and distinct then the environment is said to be discrete.eg A chess board.

Table of environments

Types of Agents - A good link

http://www.doc.ic.ac.uk/project/examples/2005/163/g0516334/gba.html

Two Major Challenges with Speech-Recognition Technology

Speech is still a relatively new interface. Technology is finally starting to catch up to the dreams that we've had since the invention of the computer itself: dreams of having natural conversations with computers—something portrayed in countless science fiction movies, TV shows, and books.

But from a UX standpoint, what does "natural" even mean?

The most popular conception of a natural conversation with a computer is one in which the user can say anything they want and the computer will understand and respond appropriately. In commercials, Appleadvertises Siri as a personal assistant that you can seemingly say anything to. This, however, is far from reality.

It’s a speech designer's job to make it seem as if users can say anything, when that’s not actually the case. Designers must develop ways to shape and constrain a user's interactions with their device. Users must be trained to communicate in an understandable manner that doesn’t make them feel like they’re tailoring the way they speak to their devices.

Users must also be made aware of what the device can do to prevent them from making errors and how to harness the complete power of the device: the two biggest challenges designing for user experience in speech recognition technology.

Feature Discovery

This is by far the hardest part of speech interface design. Speech recognition is still very new so we simply cannot recognize and do everything. Even other humans sometimes misunderstand or misinterpret what someone is saying. On top of that, people rarely look through user manuals or research everything a device can do.

Designers need to find ways to educate users about what they can do as they are interacting with devices. With touch interfaces this can be achieved through well-named buttons and high level categorization. Many speech interfaces do not have the luxury of these visual queues.

The most obvious way that people train one another is through explicit instruction. Teachers spend a lot of time lecturing their students. Parents explain to their kids that they should treat others the way they wish to be treated. This can be one way for devices to train users, but is potentially time-consuming and frustrating for experienced users. As interface designers we must find more ways to help users train themselves through self-discovery.

Another way that we teach one another is through leading by example. We don't teach a newborn to speak their first words by telling them how to shape their mouth and where to place their tongue. We speak in front of them and they experiment on their own to mimic the sounds they hear.

Nobody teaches someone to use a revolving door: we see someone else use it and copy them. Are there any opportunities for the device to lead the way in an interaction? Maybe two different virtual actors communicating for a user to observe. This method could end up being verbose but, if done well, could also be very successful considering our brains are wired to learn this way.

Bottom line: if the user can't figure out what they can do with the device they may never unlock its power, negating all of the work designers put into it.

Phrasing

People have developed many ways to express ideas, and even many ways to express the same idea. Synonyms and ambiguities are incredibly challenging elements of speech recognition from a technical point of view, forcing developers to choose between accuracy and performance. If we can design a UX that reduces ambiguity and the number of ways to phrase an idea, the system can be tuned to perform much better. If the device uses consistent phrasing the user will tend towards using the same phrasing in the future.

People frequently repeat what another person has said, with very slight variation, in order to clarify an idea. This can often be a mechanism for helping someone learn to express an idea better.

A mother teaching the difference between "can" and "may" might go like this:

"Mommy, can I have soda?"

"May you have soda?"

Designers standardizing terminology:

"When the user drags their finger quickly to the left the page should move to the next page on the right."

"Ok, so a swipe left transitions to the right page?"

This means that if we have a device that can tell time, it can be listening for the following phrases.

• "What time is it?"
• "What hour is it?"
• "How late is it?"

The device can always reply "The time is five thirty-two," queuing the user to use “time” instead of “hour” or “late.” Developers can then concentrate on making the "What time is it?" phrase work better.

Lastly, another idea for training the user's phrasing is to use non-verbal positive and/or negative feedback.People use body language to indicate if they understand what someone else is saying. They will often nod along if they understand or they may have a puzzled expression if they don't.

It would be great if we could develop a similar system for speech recognition devices. A positive tone of voice could indicate that the device understands the user very well, providing a subtle hint that they should continue to use similar phrasing. We may also flash the screen or vibrate the device to signify a positive or negative response.

Phrasing may be just an intermediate step until technology improves, but training the user to use more predictable phrasing will always improve the experience.

The Even Bigger Problem

The key to solving these problems is feedback, and here is the true difficulty: how can the device provide unobtrusive and concise feedback that helps shape the new user without frustrating the experienced one? To make this even more difficult, speech interfaces are often used in circumstances where the user cannot be looking at the device, so we can’t rely on existing paradigms of visual feedback.

There is hope, however. People are expert auditory communicators: we all do it every day. There are many things we can learn by studying how we speak with one another. What other tools can we learn and utilize to make everyone an expert with speech interfaces?

https://uxmag.com/articles/two-major-challenges-with-speech-recognition-technology

Fraud Detection Using Neural Networks and Sentinel

Fraud Detection Using Neural Networks and Sentinel Solutions (Smartsoft)

Fraud detection is a continuously evolving discipline and requires a tool that is intelligent enough to adapt to criminals strategies and ever changing tactics to commit fraud. Despite the best efforts of the FBI and other law enforcement organizations, fraud still costs American companies an overwhelming $400 billion (reference) each year. With the relatively recent growth of the Internet into a global economic force, credit card fraud has become more prevalent.

It is in a company and card issuer’s interest to prevent fraud or, failing this, to detect fraud as soon as possible. Otherwise consumer trust in both the card and the company decreases and revenue is lost, in addition to the direct losses made through fraudulent sales.

How do Neural Networks Help with Fraud Detection?

The inherit nature of neural networks is the ability to learn is being able to capture and represent complex input/output relationships. The motivation for the development of neural network technology stemmed from the desire to develop an artificial system that could perform "intelligent" tasks similar to those performed by the human brain. Neural networks resemble the human brain in the following two ways:

1. A neural network acquires knowledge through learning.
2. A neural network's knowledge is stored within inter-neuron connection strengths known as synaptic weights. The true power and advantage of neural networks lies in their ability to represent both linear and non-linear relationships and in their ability to learn these relationships directly from the data being modeled. Traditional linear models are simply inadequate when it comes to modeling data that contains non-linear characteristics.

What is Sentinel?

Sentinel is a complete solution designed to prevent, detect, analyze and follow up banking fraud in any entity or corporation in the financial business. Specific fraud detection solutions may include:

• Credit
• Debit
• ATM

With Sentinel your company can monitor the activities of accounts, cardholders and merchants by using a robust and powerful technology based on rules, parameters and indicators. In other words, you can obtain immediate results from the moment you install the software.

Sentinel allows you to:

• Process data from any origin, whether it comes from transactions, merchants or cardholders.
• Monitor issuer, acquirer or banking activities.
• Examine information by strategic business units such as countries, regions, banks, etc.
• Analyze data from a managerial perspective, through a technology known as “Business Intelligence.”
• Evaluate the performance of the rules created in the system and the profit generated by them.
• Minimize risk and loss due to banking fraud.

What is Neural Fraud Management Systems (NFMS)? The Neural Fraud Management System is a completely automated and state-of-the-art integrated system of neural networks, Fraud Detection Engine, Automatic Modeling System (AMS), supervised clustering, and system retune.

Combined with Sentinel the Neural Fraud Management System (NFMS) can automatically scale the relative importance of fraud to non-fraud, group symbols to reduce dimensionality, and evolve over time to detect new patterns and trend types in frauds.

By adding the intelligence of neural network technology to an already successful rule-based system, you can increase the detection of legitimate fraud transactions up to 80% with as low as 1% false detections or less!

How does NFMS work?

• The Neural Networks are completely adaptive able to learn from patterns of legitimate behavior and adapting to the evolving of behavior of normal transactions and patterns of fraud transactions and adapting to the evolving of the behavior of fraud transactions. The recall process of the Neural Networks is extremely fast and can make decisions in real time.
• Supervised Clustering uses a mix of traditional clustering and multi-dimensional histogram analysis with a discrete metric. The process is very fast and can make decisions in real time.
• Statistical Analysis ranks the most important features based on the joint distribution per transaction patterns. In addition, it finds the optimal subset of features and symbols with maximum information and minimum redundancy.
• The Fraud Detection Engine can apply the generated model by AMS on input data stream and output the detection results by specified model: Neural Networks, Clustering, and Combined. The Fraud Detection Engine supports both Windows and UNIX platforms.
• Retuning the basic model created by AMS to adapt to the recent trend of both the legitimate behavior and fraud behavior and update the model for Fraud Detection Engine.
• The Automatic Modeling System (AMS) chooses the important inputs and symbols, train and create clustering and neural network models.

Advantages

• Significantly reduces losses due to fraud.
• Identify new fraud methods to reduce fraud losses and minimize false positives.
• It can work in real time, online or batch modes.
• Reinforce customer trust.
• Improve operational efficiencies.
• The system could develop better models by customizing the model to the Banks unique environment.
• Build and update models as the new business requirements or changes in the environment.
• The system gives you the flexibility to easily incorporate data from many sources to the neural models.
• You have the ability to build your own custom model, in house, without being an expert in AI programming. The final user could use the wizard-based interface to create new models or change the existing ones.
• Combine multiple Artificial Intelligence technologies to identify suspicious activity (clustering, neural networks, rules, profiles).
• It provides all life cycle to avoid fraud, including the stages: monitoring, preventing, detecting, registering, learning, self building.
• Boosts analyst productivity and improves effectiveness of fraud operations.
• Non intrusive implementation and easy to integrate with standard protocols: XML, SOAP / Web Services. Additionally NFMS provides API to enable an easy integration in the Bank environment if necessary.

Success Stories

• León Bank in Dominican Republic had reduced fraud by 60% in the first 3-months of the utilization of the system.
• Guayaqyuil Bank in Ecuador had 100% detection of fraud cases in the first month.
• Credit Card Issuer Bank* saved over $3,000,000 (US Dollars) in the first 10-months of 2003 with a fraud reduction of 30% from the prior year. (Full Text PDF)

* This is the success story of one of SmartSoft’s clients, whose name they requested not to be revealed.

http://www.nd.com/resources/smartsoft.html

Artificial Intelligence in Logistics planning

Scientists at Universidad Carlos III in Madrid have presented a new technique based on artificial intelligence that can automatically create plans, allowing problems to be solved with much greater speed than current methods provide when resources are limited. This method can be applied in sectors such as logistics, autonomous control of robots, fire extinguishing and online learning. Credit: UC3M

Scientists at Universidad Carlos III in Madrid have presented a new technique based on artificial intelligence that can automatically create plans, allowing problems to be solved with much greater speed than current methods provide when resources are limited. This method can be applied in sectors such as logistics, autonomous control of robots, fire extinguishing and online learning.

The researchers have developed a new methodology to solve automated planning problems, an area of AI, especially when there are more objectives than it is possible to achieve in the available time. The idea is to get the system to find, on its own, an ordered sequence of actions that will allow objectives to be reached (in a final stage) given the initial situation and available resources. For example, given a group of trucks and goods, these techniques can use automatic planning to optimize the routes and means of transport, based on timetables and products. The methodology presented by these scientists would, in this case, allow the users to create plans in a situation in which not all the packages can be delivered, as would occur when the time that is needed to perform the task is greater than the time that is available, because of the inadequacy of the available resources. In this case, the system would attempt to find a plan by which the greatest number of goods possible could be delivered, thus minimizing the cost.
The new methodology that these scientists propose allows solutions to be found that are equivalent to or better than those provided by the other existing techniques, in addition to doing so much faster, when there are limited resources that can be used. "With regard to time, our technique is three to ten times faster, and with regard to quality, our solutions offer similar quality to that obtained by the best technique that is currently available", states one of the researchers, Ángel García Olaya, of the PLG group (Planning and Learning Research Group) of UC3M's Computer Science Department. "Now – he points out – we are making modifications that we hope will allow us to give still greater quality to our solutions". This study has been presented at the most recent Conferencia Española para la Inteligencia Artificial (CAEPIA – Spanish Conference on Artificial Intelligence) in Tenerife, where it received the award for the best article. In addition, it has recently been published in Lecture Notes in Computer Science by Springer. This research at UC3M has received funding from the Autonomous Community of Madrid and the Ministry of Science and Innovation.

This new methodology can be applied in any sector in which is makes sense to implement automatic planning, as is already done in the cases of extinguishing fires, autonomous control of robots, on-line learning, logistics, etc. In this last field, in fact, these researchers have already carried out a project with Acciona for managing their logistics division; it was subsidized by the Ministry of Industry, Tourism and Commerce. To be specific, they created a system of automatic planning for multimodal transport of goods. The data that was provided to the system included the position of the trucks, as well as the schedules of the transport ships and trains, together with the characteristics of the clients' orders (situation of containers, route, type of merchandise). With this information, the system first decided which truck and container should carry out each part of the service, to then calculate the route to be taken, the order in which the items would be delivered and, if necessary, to change the method of transport (truck, train and/or boat).

"What very often happens in real situations is that there is no plan that can reach all of the objectives due to the limitations of one resource, such as time, money, fuel, battery... and this is where the methodology proposed in the article can be used", explains Professor Ángel García Olaya. The researchers have tested it in a series of realms that simulate real situations and that occur frequently in the field of planning; it has already been integrated into an architecture for the autonomous control of robots that the group is working on. In fact, NASA has already used automatic planning for the autonomous control of their rovers, Spirit and Opportunity, which traveled to Mars a few years ago. In that case, they used a mixed initiative system in which the rovers' operators used a planner to create the plans (movements, sample taking, photos, etc.) for the two automated vehicles. The planner took all of the operating restrictions into account and created a plan that could be modified by the operators. Later the plan, which had been conveniently checked to avoid any inconsistency, was transmitted to the rovers so that they could execute it. Currently, the PLG group is applying the techniques developed in a project carried out with the European Space Agency (ESA) on the planning of observation operations in space.

http://phys.org/news/2012-01-artificial-intelligence-technique-tasks-resources.html

chinese room

http://en.wikipedia.org/wiki/Chinese_room