La resolución de Problemas de Satisfacción de Restricciones (PSR, por sus siglas en español, o CSP por sus siglas en inglés) es un conjunto de técnicas utilizadas para la descripción y posterior resolución efectiva de grandes y complejos problemas, particularmente combinatorios, que aparecen en muchas áreas de la vida real y que se caracterizan porque sus soluciones se pueden expresar por medio de un conjunto de variables que deben verificar algunas restricciones simultáneas. Este tipo de problemas aparecen en áreas como Inteligencia Artificial, Investigación Operativa, Bases de Datos, Sistemas Expertos, Sistemas Económicos, etc. y se aplican a problemas de scheduling, planificación, razonamiento temporal, diseño en la ingeniería, empaquetamiento, criptografía, diagnosis, toma de decisiones, etc. En esta entrada vamos a presentar una introducción de los conceptos y algoritmos fundamentales de PSR.
This post has the goal to serve as guide for the session "Programming Mathematical Models ... with NetLogo" from the 5th International Summer School of Mathematics in Seville, between July 15th and 31st 2016.
For this reason, this post is more like a set of notes to focus our achievements that something to read from outside... sorry for those coming from outside the Summer School, as it can be of little interest for them. We will build a model to experiment with totallistic 2D Cellular Automata from scratch (and provide some optimizations for the Game of Life case).
Following with the simulation of Classical Elements in NetLogo, and after Earth and Water, we will address in this post how to simulate some fire features, but taking into account the same goals of decentralized and as simple as possible models.
Fire is formed by a set of incandescent particles or molecules of combustible material capable of emitting visible light. The flames are the parts of the fire that emit visible light, while smoke are physically the same but that no longer emit. Because the most common and graphical picture of fire is the flame, we will be interested in this post in simulate flame productions.
After Earth, and to continue with the simulation of Classical Elements in NetLogo, in this post we will give some simple, but very graphical and good looking, models to simulate the behaviour of water.
In this post we will simplify so much the assumptions that the model we will obtain only will be useful to simulate liquids under some conditions, but not gasses. You can find very realistic and nice simulation of different fluids behaviours under several and more general assumptions, but here we will give only a fast and simple way to obtain a behaviour that we visually recognize as a liquid.
With this post we begin a series of posts that aim to simulate the creation and behavior of the 4 classic elements of nature in NetLogo: Earth, Water, Fire and Air.
In this first post we will see one of the most classical algorithms for the formation of realistic landscapes: the mid point displacement algorithm. This algorithm handles only generate a map of heights above a defined level, then apply a flooding process, color and shading to create more realistic results.
In this post we present how to implement Self Organizing Maps (Kohonen, 1992) in NetLogo. Specifically, we will implement two versions, a first introduction example to project 3D colors in a 2D plane, and a second one where we can input a file with N-dimensional data and it will make a projection to 2D space mantaining the topological structure of the original vectors.
As a way to continue with AI algorithms implemented in NetLogo, in this post we will see how we can make a simple model to investigate about Artificial Neural Networks (ANN). We will restrict ourselves to the more common and classical ones, the Multilayer Perceptron Network... my excuses for those of you that are waiting to see here something about Deep Neural Networks (DNN, as those used in AlphaGo from Google, or CaptionBot from Microsoft), maybe in a later post I will try to think about how to extract the main features of some convolutional neural network and test it on a very simple NetLogo model, but I am afraid that we will need too many computational resources to obtain anything of interest with this tool... Who knows? I will keep thinking.
In this post we will see implementations of a couple of methods that, starting from initial states, will search in the state space by local moves that take us closer to the solution. As the space is more complex and bigger, more difficult is to find the solution, hence we will not be interested in the best path to reach the goal, and maybe we don't obtain the goal in a minimal time, but sometimes is good enough to reach it or to find a state that is very similar to one solution (that is, sometimes we change the best solution for a good enough one).
Among the different search algorithms that make use of partial information by using heuristics, the most famous is the A* algorithm, and in this post we will present several implementations of this algorithm in NetLogo, from a basic application of A* to be used a pathfinding algorithm in 2D grids to a more general version where we give some reports to be used as general problem solver.