Crackpot

In our lab, we are building a real-time planning system in C++, called Crackpot. A planning system can reason about which set of actions need to be taken in order to achieve specified goals. For example, if a robot Wall-e is asked to fetch a drink from the local store, it must internally generate a plan to reach the store, buy the drink and then return back home.

In our related games lab, Crackpot will be used in a story planning project. It will serve as an engine to automatically develop plans or "recipes" for story content generation, with the goal to optimize player experience.

Crackpot is a general (the technical term is domain-independent), real-time, dynamic planning system. Being general, it can be used for automated planning across diverse applications.

Crackpot is a public domain, open source software. See https://sourceforge.net/projects/crackpot/. See also my blog on Crackpot.

Presentation Review: How the Computational Perspective is Transforming the Sciences

Occasionally I will review interesting talks and papers.

In this talk, Papadimitriou speaks about how computational aspects of sciences have influenced the sciences and are leading to several important results. He touches upon several sciences: quantum physics, statistical mechanics, biological systems, game theory, social networks, economics and brain as he explains how they are deeply interacting with computer science.

Quantum computers can be used to solve problems which otherwise take an exponential amount of time. However, the existing quantum computer experiments work for small number of particles (~6), which translates to quantum algorithms succeeding only for small inputs. As of now, it is unclear whether quantum computers can be built for large inputs. This is a question of testing the theory of Quantum Physics. As Umesh Vazirani says "Quantum computation is as much about testing Quantum Physics as it is about building powerful computers".

In statistical mechanics, when parameters of local interactions evolve, macroscopic properties
change dramatically, and we have a phase transition (melting of solid into liquid is an example). In computer science, certain randomized algorithms are known to converge exponentially faster when the parameters are in the right range. A deep fact is that two phenomena are indeed the same. The same phenomena also occur/used in coding theory and artificial intelligence, as this reference explains.

Then Papadimitriou moves on to explore the relation between biological systems and computer science. One example he shows is a 2006 paper "An optimal brain can be composed of conflicting agents" in which the authors find that "under natural physiological limitations, an optimal decision-making system can involve ‘selfish’ agents that are in conflict with one another, even though the system is designed for a single purpose." This result is on common ground between artificial intelligence multi-agent systems and theory of evolution in biology.

The next biology example is related to Charles Darwin's statement "To think that the eye could evolve by natural selection seems, I freely confess, absurd to the highest degree” considering that such an evolution might be highly improbable. Leslie Valiant in a recent paper "Evolvability" suggests a theory to "explain quantitatively which mechanisms can evolve in realistic population sizes within realistic time periods, and which are too complex. If evolution merely performed a random search it would require exponential time, much too long to explain the complexity of existing biological structures." Natural selection has been used for decades in solving large search problems in artificial intelligence and computer science.

The third biology example involves population selection processes used in search in artificial intelligence and computer science (also on the lines of Darwin's theory of selection). Simulated annealing and genetic algorithms are widely used search methods. In these methods search is carried out by a population of search "threads" - and these threads evolve through a selection process in each "generation" of threads. Simulated annealing is akin to asexual reproduction. Genetic algorithms are akin to sexual reproduction. Simulated annealing works so much better than genetic algorithms in solving optimization problems. Why is that? As per a recent paper "Genetic Modularity" by Livnat and Papadimitriou (yet to be published), sex favors variance over optimization. This also means sex favors creation of new species.

Internet is a large system that was never designed and its study is akin to the study of natural processes and social science. In game theory, Nash and other proved the existence of equilibria, which are predictions of behavior. Computing equilibria can be used to predict the stock market, for example. A recent result (paper here) says that computing a Nash equilibrium is an intractable problem.

In social networks, recent results (paper) show that "it is a small world". That is, most people are within a few "hops" or connections from you. This result follows from maths developed for study of internet viz how many routers does a packet have to traverse to reach its destination.

Link to the original presentation.

Course on Knowledge Based Systems - CS4244

This course taught about rule based systems. We used the CLIPS language to implement rules,. CLIPS automatically combines rules to perform a complex task. The course content topics included knowledge representation, knowledge acquisition, representing uncertainty including DS-theory, Classification and Construction Problem Solving, and basics of other kinds of knowledge based systems like Blackboard Systems, Case Based Reasoning, Machine Learning (ID3, Candidate Elimination) and Truth Maintenance Systems.

We encountered the following systems: STRIPS (planner), MYCIN (medical diagnosis rule based system), EMYCIN (empty mycin), R1/XCON (configuration of computer systems), CENTAUR (explanation system), MOLGEN (genetic experiment planner).

Book we followed: Engrossing book by Peter Jackson: "Introduction to Expert Systems"

We did a project on "Weekend Itinerary Planning". Here is the report. The planner had the following major components: itinerary generation, event selection, travel selection and user interface.

From this course, I generated two ideas for "good things to have":

1. An Itinerary Planner for Weekend Travel (not just a toy project but on WWW);
2. A Rule Based Library in C++/Java based on CLIPS engine - with one use in Computer Gaming.

See also:

1. Peter Jackson's Expert Systems reading list
2. Another course in a related field
   

My Research

I am interested in artificial intelligence, automated planning, parallel computing, multi-agent systems and optimization.

Right now I am working in a central field of Aritificial Intelligence called Automated Planning. Specifically, I am looking for ways to scale Planning on modern computers. In our lab, we also apply our Planning technology to story planning in games. I was previously a software developer and in the future want to apply AI as an entrepreneur. Only time can tell what I will do afterwards.

A Simple Overview of Artificial Intelligence

Artificial Intelligence is applied not only to robotics, but also corporate decision-making, building large-scale systems, operations research, medicine, computer games and many other fields. If mathematics is the queen of sciences, AI must be the queen of computer sciences. More on this soon ...

My Team's Research on Automated Planning

Automated Planning studies how an intelligent agent can combine actions in order to reach specified goals. An intelligent agent with ability to plan can "think ahead". Automated Planning systems have been used where human involvement is difficult or partial (like space missions, elderly assistance), or problems are quite complex (like composition of web-services) or little time is available before execution (like computer gaming, emergency evacuation). While previously most researchers studied planning for simplified toy problems, nowadays many researchers study how planning can be used in the real world. In our lab, we are building a real-time, responsive AI Planning system (see: What is Planning?) affectionately called Crackpot. Our lab is headed by my supervisor Alexander Nareyek. Another team in our lab will use Crackpot for automated experience/story generation for games/training.

My Research

Modern computers are different from computers in the 20th century. They implement a large degree of parallelism; the parallelism is increasing every year. Software systems must be designed and implemented differently to run on these parallel computers. We study how real-time AI Planning can be implemented to effectively utilize the resources of these parallel computers.

Some Ideas on Entrepreurship

AI is much more in the books and labs than in the real-world applications. Decision Support, Case-Based Reasoning and Expert Systems have been widely used previously. However, planning and scheduling are largely unexplored areas till now.

Some Ideas to Stumble Upon Further in the Future

Agent-Based Simulations looks quite interesting. Large scale simulations of human/human-like agent communities can be carried out for purposes of hypothesis testing and prediction.

What is Planning?

From the book Automated Planning by Ghallab et al:

Planning is the reasoning side of acting. It is a deliberation process that chooses and organizes actions by anticipating their expected outcomes. This deliberation aims at achieving as best as possible some prestated objectives. Automated Planning is an area of Artificial Intelligence (AI) that studies this deliberation process computationally.

As opposed to an ordinary control program, a Planning System or Planner would be more flexible and able to take advantage of opportunities in a dynamic environment. Usage of a Planner may also decrease cost in some situations due to lesser involvement of humans.

Here is an example scenario of planning:

When a robot Wall-e is asked to fetch a drink from the local store, it must internally generate a plan to reach the store, buy the drink and then return back home. While going out, when Wall-e identifies that the door of the room is closed, it must update the plan to include an action to open the door and close it on the way out.

Some real life applications of planning:

• NASA used Autonomous Remote Agent system based on planning and scheduling techniques on board Deep Space mission. The Remote Agent was able to generate plans and execute high-level commands like “during the next period, take pictures of the following asteroids”.
  
• Robot motion planning, and goal-directed planning
  
• Process planning is the task of preparing detailed operating instructions for transforming an engineering design into a final product.
  
• Autominder is a Planning, Monitoring and Reminding Assistive Agent for the Elderly.
  
• Emergency evacuation planning
• Simulated environments like training and games use goal directed planners.
  

Our Work

At Interactive Intelligence Lab we are building a widely applicable real time, dynamic and efficient planning system. The planning system will be first applied to Automated Story Generation in Computer Gaming.

See Also: AAAI Page on Planning and Scheduling