Vista previa del material en texto
Métodos modernos de Inteligencia Artificial Grigori Sidorov (Ed.) México D. F. 2011 ______________________________________________________________________________ Prefacio Este libro contiene los trabajos de los especialistas prominentes en el área de la inteligencia artificial quienes en su mayoría trabajan en México. La idea principal de este libro es dar a conocer a los lectores el estado actual de algunos de los métodos más utilizados de la inteligencia artificial moderna. Los autores de este libro hicieron un gran esfuerzo para presentar a sus lectores un libro práctico y escrito de manera clara. Aquí se tratan los temas que es difícil encontrar en un solo libro especialmente redactado en el español. Además con diferencia a los libros clásicos de la inteligencia artificial aquí se presenta la información mucho más actualizada ya que es un libro mucho más reciente y presenta los últimos avances en el campo. Por su diseño, es un libro de texto orientado a los estudiantes de todos los niveles —licenciatura, maestría y doctorado, y al público en general interesado en la inteligencia artificial. También el libro puede servir como un libro de consultas y ser útil para los especialistas de diferentes áreas —no solo en el área de la computación— quienes buscan la posibilidad de aplicar los métodos de la inteligencia artificial en sus áreas de conocimiento. El libro tiene un enfoque práctico, es decir, está orientado a solución de los problemas prácticos que pueden presentarse tratando de aplicar algunos de los métodos de la inteligencia artificial. Cada capítulo tiene un número suficiente de los ejemplos prácticos de aplicaciones de los métodos y al final se proponen algunos ejercicios como un reto para los lectores a aplicar los conocimientos obtenidos durante su lectura. Este libro no requiere conocimiento profundo previo ni de las matemáticas, ni de la computación, sin embargo se espera que el lector esté familiarizado con las ideas básicas de que es un algoritmo, cómo se escribe un programa, y sepa los conceptos fundamentales de las matemáticas. Los temas principales abordados en el libro son los métodos de aprendizaje automático, optimización, razonamiento, y sus aplicaciones. Más específicamente se describen los métodos de búsqueda heurística, programación lógica, algoritmos genéticos, los paradigmas de optimización emergentes (evolución diferencial, optimización mediante cúmulo de partículas) las redes neuronales, aprendizaje por refuerzo, las ideas básicas de razonamiento temporal, solución de problemas usando agentes inteligentes y utilización de esos métodos en la robótica móvil. También se abarcan las ideas básicas relacionadas con el diseño de las ontologías, representación de conocimiento y su uso en práctica (sistemas expertos). Después de leer este libro el lector sabrá cómo aplicar varios métodos de la inteligencia artificial a una amplia gama de problemas. Grigori Sidorov México D. F. a 10 de enero del 2011 3 4 ������ �� �� ����� �������� ���� ���� ������� � ��� ��� ���� ��������� � ��� � ������ � . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �� �������� � ����� �� � �������� . . . . . . . . . . . . . . . . . . . . . . . . �� �������� � ���������� � � �� � ������� � � �������� ��� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �� �������� !����������� ������ ��� ��� ���� ��������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �������� " # � � � ������ �$ ������ ������ � ��������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �������� % ����������� &�����&� . . . . . . . . . . . . . . . . . . . . ��� �������� ' !��������� � �� �� � � ���������� ���(���������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �������� ) *� �� � ��� ��� �� � � ���� ��� ������� �� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �������� + !��� ��� � � ������ � ,��-�& � ��� ���.�/ ��� � 0� �.� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � �������� 1 # �� � ������� � ��.����� ��� � ������ � ��� ��� ���� ��������� . . . . . . . . . . . . . . . . . . . . . . �� �������� #������� ������ � � ���������� ��� � � 5 ������ ���� �� !� 0���� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2����������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �������� ���� ���� ������� � ��� ��� ���� ��������� � ��� � ������ � . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �� �� � ������ ��� ��������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ������� ��� ������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ���� ��� �� ��� ���� ��! � ������ ��� � � � � � � � � � � � � � � � � � � � ���� ���� ��� �� ��� ���� ��! � ������ ��� �������� � � � � � � � � � � � �� "��� �� �� ��� #��� �� �� � ������ ��� ��������� � � � � � � � � � � � � � � � � �� �$����� �� � ������ ��� ��������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �������� � ����� �� � �������� . . . . . . . . . . . . . . . . . . . . . . . �� �� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ���� ��� � �� ��&���� �� ������� � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� '�&���� ����% �� ��� &��(��)�� � ��&���� �� ������� ���� "*�)&��� �� ��� ��&����� �� ������� � � � � � � � � � � � � � � � � � � � � ���� "���������� �� (��� ��� � ��� ��&����� �� ������� � � � � � � � ���� ���� ��� � ������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � ���� ��� +� ������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � "�&������ �� �� (��� ��� +� ������� � � � � � � � � � � � � � � � � � � � �� ���� ��� (����� � �� ��� ���% ��� &��(��)� � � � � � � � � � � � � � � � ���� "� )$���� �� ��� ���% ��� &��(��)� � � � � � � � � � � � � � � � � � � ���� ,��-�� ./0� ,��-� �� ������% � � � � � � � � � � � � � � � � � � � � � � � � ���� "*�)&��! �� &��(��)� �� � �������% ��)(%���� � � � � � � � � � � ���� "�&������ �� (��� ��� � ���-�� ./0 � � � � � � � � � � � � � � � � � �� � ���� ��� � &��- ����� � ��� #�(���� ./0 � � � � � � � � � � � �� � 1�-��� ���� 2 �&�������� ���3� � � � � � � � � � � � � � � � � � � � � � � � � �� ���� ��� � ��� #�(���� �� * ���� � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 4������)�� �� )� �)�5 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 4������)�� �� ��-�6(��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 6 �������� � ���������� � � �� � ������� � � �������� ��� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �� �� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 7 � �&��5�)���% � �� ��� ���% �� �� ���)�� �� � � � � � � � ���� 8�&�� �� �� ���)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� '�&���� ����% ��� �� ���)�� �� 2 ��9� �)�� �� � � � � � � � � � � � � � � ���� :%���� ��#���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� '�&���� ����� �� ���� �� ����� � � � � � � � � � � � � � � � � � � � � � � � ���� ;����)�� �5&����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� �� �*� �� � ������ )(�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� '�9� �)�� �� &��(�(��������! ����� (�2���� �� � � � � � � � � � � ���� <������� �� ������ )(�� � � �� � � � � � � � � � � � � � � � � � � � � � � � � � � ���� :%���� 1�- �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� 0 �������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 1�� ���� �� �� � ������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� =�)&� � ��� �� � � ������� � � � � � � � � � � � � � � � � � � � � � � � � ���� 8�&�� �� � �������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � =�����% �� � �������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � "*�)&��� �� � �������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �������� !����������� ������ ��� ��� ���� ��������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� 7 &��)�� �� ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� :� �� ��� ���% �� &�����)�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� :� � ���������% �� &�����)�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� :� ��� ���3���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� :$5��� 2 �� ��5�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ;�)# ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ;�)# ���� ���������3� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ;�)# ���� &����� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� � �� �� � ���� ���������3�/&����� ����� � � � � � � � � � � � � � � � � � � � � � � � =� ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� "� ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� "� -���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� :� �����% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � :����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� "3�� ���% &���9��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� "� &�������� -���9�/� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� "� &�������� >+� /� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� 0&�������� 2 ��&������ �5&����3� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� �&�� ��9�*� � ��)#���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 7 �������� " # � � � ������ �$ ������ ������ � ��������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �� � ���� ���% � ��� ����� � �� ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� =� ��&��� (#����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� ������ �� ��� ��)& ����� �%����� � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� '���� �� 3����� ��&�� 2 � � ��� �)�� �� � � � � � � � � � � � � � � � � � � � � �� �� 7�� �� ����� � �� ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ���� 4��/4��� &������)�� �� �� ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ���� " ��� � �� � ��� � �� �� &��� ��� - ��� �� ����� �)$������ � ��� �� =� ��������� �� &�#������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� "� �� * �� �� ����� �� � ��� �)�� �� � � � � � � � � � � � � � � � � � � � � � � � ��� ���� 1���?� �� ����� � �� ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� "� &������ �� � ��� �)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� � ������9���% �� �� ��)&���� ��) ���� � � � � � � � � � � � � � � � � � � � � � � ��� �� � � ������9���% �� �� �������)�� �� $����� � � � � � � � � � � � � � � � � � � � � ��� �� � 8�&�� �� � ��� �)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� " ��� �)�� �� �� (��@6&��&������ � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� " ��� �)�� �� �� �� �������% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� '�� ���% �� � ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� '���� � ��6��������3�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� '�� ���% �� � ��� � ��?���� &���%����� � � � � � � � � � � � � � � � � � � � � � ��� ���� '�� ���% �� � ��� � ��?���� �6&���%����� � � � � � � � � � � � � � � � � � � ��� � 7�� �� � ��� � �� �� ��)� ����������� � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� � ���� ���% � ��� ������������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� :� )����9 �� �� - ��% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� =���������% )$���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� � '���� � �� ���� ��)&��*�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� � ���� ���% � ��� ����� � �� ���� ��)&��*�� � � � � � � � � � � � � � � � � � ��� ��� :� ����-��)��� �� <� ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ��� 7�� �� ����� � �� ���� �� �)���� ��)&��*�� � � � � � � � � � � � � � � � �� �� "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� �������� % ����������� &�����&� . . . . . . . . . . . . . . . . . . . . ��� �� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� 0&��)�9���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� 0&��)�9���% � ������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� �$����� �� �&��)�9���% (������ � ������ �� � � � � � � � � � � � � � � � � ��� �� ���� ��� ��������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� '������� ��) ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � "3�� ��% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� 1��>� A ���&��(������ 2 �3�� ��% � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� � �������)�� �� $����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� =��)���)�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� �������)�� �� $����� �� ���������% (� ���� � � � � � � � � � � � � � � � � � � � � � � ��� 8 ���� '�&���� ����% �� &��#)����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� 4�(����% � ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� ;������% �� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� �&����)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� � 1���� �� ��� � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� � � ����% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� �������)�� �� $����� �� ���������% ���� � � � � � � � � � � � � � � � � � � � � � � � � � �� ���� 4�(����% � ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ���� �&����)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ���� =� 9�)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ���� � ����% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� =��� �� ��� ���! �������� �� �)#�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� 4�����)���% �� $���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ����� =� 9� � &�����)���% �� $���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ����� � ����% � &�����)���% �� $���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � ����� ,� �����% �� �� &�(����% � ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ����� "� &������ �3�� ��3� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� � =��� �� ��� ���! )������� �� �)&����� � � � � � � � � � � � � � � � � � � � � � � � � ��� � =� ��&��� �� �� ��(������ � � ����� � � � � � � � � � � � � � � � � � � � � � � � � � � ����� ������� �'��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ����� '�� ������! )������ �3����(��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ����� '�� ������! )������ ) ���3����(��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � ������'�� ���% ��� �� * �� �� - ��� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � ������=�)&�����% � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� =� �� ��� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� '�-��� ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �������� ' !��������� � �� �� � � ���������� ���(���������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �� � ���� ���% � ��� +� �������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� 1�-��� ��� &��(��)�� &�� �����3�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� �$����� ��#����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� B4�� � $ ����9�� +� ��������C � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� D� �������� � (��6� �&������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� � D� �������� (��6� �&������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� � =�)&� � ��� �� �������)� (��6� �&����� � � � � � � � � � � � � � � � � � � � �� �� "3�� ��% 1�-��� ���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� ����3���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� "��)� ��� �� �� "3�� ��% 1�-��� ���� � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� E���� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� "*�)&�� �� - ��� �)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� 4;0 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� ����3���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� 9 ���� "��)� ��� �� �� 0&��)�9���% ����� �� =�) ��� �� 4����� ��� � � ��� ���� E���� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� "*�)&�� �� - ��� �)�� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� '�� )� 2 �� �� ���� - � ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� � "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �������� ) *� �� � ��� ��� �� � � ���� ��� ������� �� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ��� �� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ��� ��� � ������ ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� � ������ ��� +���%����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 4��&������� �� ��� ��� � ������ ��� � � � � � � � � � � � � � � � � � � � � � ���� 8�&�� (#����� �� ��� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ;����)�� ) ���6��� �� �� ��� ��� � �� ��� ���� � � � � � � � � � � � � � � � ���� <��)���9���% �� ��� ��� �1� � � � � � � � � � � � � � � � � � � � � � � � � � ���� � �������% � ��� ��� ��� �1� (����� � ����� � � � � � � � � � � � ���� "*�)&��! �5&������% �� &�� ��� � � � � � � � � � � � � � � � � � � � � ���� ��� ����� ��� �� ��� ��� �1� � � � � � � � � � � � � � � � � � � � � � � � � � �� � �������� �� �������� � ;�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ���� ��)�� �� � �������% � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ��� ��� ���&�����3�� 2 ��� ��� � ��6� ��������� � � � � � � � � � ���� ���� ��)�� �� ��������% � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� <��)���% �� �������� �� �� ��� ��� � � � � � � � � � � � � � � � � � � � � � =�) �����% � ��� ��� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� :� � �*� �� ��) �����% �� ��� ��� F�=:G � � � � � � � � � � � � ��� :� � �*�� �� �� �� ��� 2 � �������� � � � � � � � � � � � � � � � � � � � � �&�� ��9�*� � �����)�� ) ���6��� �� � � � � � � � � � � � � � � � � � � � � � � � � ��� �&�� ��9�*� �������3� (����� � �� ������ �� � ������ ���� �������3�� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� "*�)&�� �� �&�� ��9�*� �������3� &��� �� � ��� �� ���(�*�� �� 1��������� �� ��� ��� � ������ ��� 2 ;�� � � � � � � � � � � � � � � � � � � � � � ���� :� � �*�� �� &�����)���% �� ��� ��� � ������ ��� � � � � � � � ���� 4����-��)�� �� ��� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� =� �� ��� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �������� + !��� ��� � � ������ � ,��-�& � ��� ���.�/ ��� � 0� �.� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . � � �� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� 4������� �� 1�����% �� ���@�3 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� �14� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 40�14� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� �$����� �� ;�� ��% �#����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 4�����)���% 1� #)��� F14G � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 10 ���� �� �� =���� F�=G � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� �&�� ��9�*� &�� '�- ��9� F':G � �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� 8$� ���� �� ;�� ��� �� �3� 9���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 8��9�� �� "����(������ F����������� �� ��G � � � � � � � � � � � � � � � � � � � � � � � � ���� 4�� ������% 2 �&�� ��9�*� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� ,� �����9���% � �&�� ��9�*� &�� '�- ��9� � � � � � � � � � � � � � � � � � � ��� � '�&���� ����� �� <������9���� 2 �(�������� � � � � � � � � � � � � � � � � � � � � � � � ��� ��� '���� ��2���� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� �14� <������9���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� ��������% �� ������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� �&�� ��9�*� &�� '�- ��9� '������ �� � � � � � � � � � � � � � � � � � � � � � � � � � ��� � 8$� ���� �� 1����)&�����% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� 1���)&�����% *��#�� ��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ��� 0&��� � � �����6����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ��� D��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� ��� ��HI� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� � � 1���)&�����% =� � ��� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� �&������� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� �&�� ��� �� � E���� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� =� ���� �� � 4�� �� "�$������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� D�)��! "� ��(�� )� ��*��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� =� �� ��� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �� "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� �������� 1 # �� � ������� � ��.����� ��� � ������ � ��� ��� ���� ��������� . . . . . . . . . . . . . . . . . . . . . . �� �� � ���� ���% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� 8������ 2 )������ ��)&������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 4��)���3�� ��)&������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ,������� � ���%���� �� ��� ���)� ��� ��)&������ � � � � � � � � � � ���� =���������% �� ������� �� �� �� ���� ��)&���� � � � � � � � � � � �� " -�� �� ��)&������ � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� �$���� � � ����9� &��#)����� ��)&������ � � � � � � � � � � � � � � ���� :%����� ��)&������ )������ � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� :%����� ��)&������ )��������9���� � � � � � � � � � � � � � � � � � � � � � � ���� :%����� )��������9���� 3�� �%����� �6)��������9���� � � � � � � �� �)&��� ��)� �� )��� &��������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � =���������% �5+� ���3� �� &��&������ �� ��)&������ � � � � � � � � � � � � �� ������� �� �� �� 2 �*�)&��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� '�&���� ����% ��� � ��� �� ��3���� � � � � � � � � � � � � � � � � � � � � � ��� '�&���� ����% ��)&���� � ������3�� � � � � � � � � � � � � � � � � � � ��� '�9� � �� ��(�� �3� ��A ��)(�� 2 �� ������� � � � � � � � � � � � �� =� �� ��� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 11 �������� #������� ������ � � ���������� ��� � � �� "��)� ��� �� �� ��(%���� (����� � �� ��)&����)�� �� � � � � � � � � � � � � � � � ���� =�������������� ��� � -�� � (����� � �� ��)&����)�� �� � � � � � � � � � ���� E���% )�� ��� 2 �)���� �� ��� )������� �� �� � ���� � � � � � � � � � � ���� E� ��*�� ��� � -�� � (����� � �� ��)&����)�� �� � � � � � � � � � � � � � � �� "��)� ��� �� �� ��(%���� �3�� ��3� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� ��� �������% �� ��� ���)� ��� � �3�� ��� �� � � � � � � � � � � � � � � � � � � � � ���� "� ����?� �� �� - ��% �� ������� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� 1���?� �� �� � ���� �)&��� �� �3�� ��% ��������� � � � � � � � � � � � � � � �� 7 )��� ��)� �� �����9��� �� � �������% �� � -��)���% &��� �� �������% �� ����% � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���� =�;;<A � ��� ����� �� �� ���� �� �������% � � � � � � � � � � � � � � � � � � � ���� 1��������� �� �� � ���� &��� =�;;< � � � � � � � � � � � � � � � � � � � � � � � � � � ���� '�� ��� �� ��� ������� �� �� ����?���� + )� � � � � � � � � � � � � � ��� �� '���� ��% �� ������ &�� )���� �� �������% �� ����% � � � � � � � � � � � � � � ��� ���� "� ��(�� J+�&��� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� ���� �)&���� ��� ��� �� �� ��) ����� ��(%���� 2 ��(�� ���� � � � �� ���� "*�)&��� �� �5&���)� ��� �� �� ��(�� J+�&��� � � � � � � � � � � � � � � � �� � =� �� ��� �� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� � "*�������� &��& ����� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��� *���� � � ��� ��������� . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . �� 12 Introducción Este libro describe los métodos que se encuentran en el foco de atención de la inteligencia artificial moderna. Por esta razón, nos centramos en la parte dinámica de la IA, la parte que se puede considerarse como estática, relacionada con representación de conocimiento, queda no cubierta en nuestro libro; sugerimos al lector consultar otros libros. También nótese, que este libro presenta el estado de arte de los métodos de la IA haciendo el hincapié en su estado moderno, sin embargo, por supuesto, existen las consideraciones clásicas que no pudimos omitir para tener un panorama completo. Todos los capítulos contienen ejemplos detallados de funcionamiento de los algoritmos y métodos correspondientes. El capítulo 1 presenta el análisis de los conceptos básicos de inteligencia artificial, tales como la propia inteligencia y la inteligencia artificial, implementando un análisis lingüístico basado en las definiciones que se encuentran en diccionarios. También se analiza la estructura del área de IA tomando en cuenta el flujo de información en nuestra interacción con el mundo externo. En el Capítulo 2 se presentan las búsquedas heurísticas. Se discuten la búsqueda en el espacio de estados y la búsqueda basada en la reducción del problema. También se presentan el procedimiento minimax y el procedimiento alfa-beta. El Capítulo 3 se dedica a los problemas relacionados con la representación del conocimiento. Se presentan sistemas expertos, manejo de incertidumbre, y se discuten los problemas relacionados con la creación y utilización de las ontologías. Los temas relacionados con la programación lógica se presentan en el Capítulo 4. Se describe como desarrollar un programa un Prolog. Se introduce el concepto del árbol de resolución. Se discute semántica y control de los programas correspondientes. En el capítulo 5 se da una introducción a las redes neuronales artificiales. Se presentan varias consideraciones prácticas de su uso. Se ven los casos de aplicaciones tales como reducción de ruido (redes auto-asociativas) y clasificación (redes usadas como clasificadores).El capítulo 6 es una introducción a la computación evolutiva. El capítulo cubre tanto las bases teóricas que la sustentan como una interpretación intuitiva de los conceptos importantes del área. 13 En el capítulo 7 se presenta una introducción a los algoritmos bio- inspirados. Son un concepto de reciente creación. En primer término se presenta un panorama de las heurísticas para resolver problemas de búsqueda, se propone una clasificación basada en la motivación de cada una de ellas y se introducen los elementos que todo algoritmo bio-inspirado tiene. Posteriormente, los dos algoritmos bio-inspirados más recientemente propuestos en la literatura especializada se describen a nivel más detallado: La Evolución Diferencial (ED) y la Optimización Mediante Cúmulos de Partículas (PSO). Para cada uno de ellos se explica la forma de representar soluciones a un problema, la manera de escoger aquellas soluciones —llamadas individuos en ED y partículas en PSO— que guiarán a las demás soluciones en el proceso de búsqueda, los operadores que permiten generar nuevas soluciones a partir de las ya existentes y las técnicas para mantener aquellas mejores soluciones en la población (en el caso de la ED) y en el cúmulo (en el caso de PSO). El capítulo 8 da una panorámica de los agentes inteligentes. Primero los agentes se presentan desde una perspectiva individual. Es decir, primero se caracterizan este tipo de agentes, se exponen algunos de los mecanismos más comunes de razonamiento práctico. Después, se presenta la descripción de los agentes inteligentes desde una perspectiva colectiva: los sistemas multiagentes. Se exponen los mecanismos de interacción y negociación más comunes; así como, los métodos de comunicación y coordinación en este tipo de sistemas. El capítulo 9 presenta una introducción a los procesos de decisión de Markov (Markov Decision Processes, MDP, en inglés) y el aprendizaje por refuerzo. Se muestra como el problema de planeación puede ser representada como MDP y se describen los algoritmos básicos de su solución. También se presentan métodos de solución para problemas más complejos, mediante modelos factorizados y abstractos. Se ilustran estos métodos en tres aplicaciones: aprendiendo a volar un avión, controlando una planta eléctrica y coordinando a un robot mensajero. El capítulo 10 discute la representación y razonamiento temporal. Muchos sistemas de la inteligencia artificial necesitan manejar la dimensión temporal de la información, tomar en cuenta los cambios en la información y poseer el conocimiento de cómo se cambia. Se presenta una descripción de algunos problemas fundamentales de las teorías y modelos temporales usando las consideraciones ontológicas del tiempo y de las relaciones de la orden temporal. Se da a conocer los tres enfoques principales a la representación de la información temporal en la IA y se proporciona una clasificación más fina de las proposiciones temporales. En el capítulo 11 se describe el campo de la robótica basada en comportamiento. Para sentar las bases de la robótica basada en el comportamiento se presenta un enfoque reactivo donde la emergencia de las conductas hace posible resolver problemas relacionados con la selección de acción. Este es un problema recurrente donde varios subsistemas tratan de 14 acceder al mismo tiempo un recurso compartido. Se presentan también los elementos de robótica evolutiva, es decir, basada en el comportamiento animal. Existe una amplia gama de aplicaciones industriales de robots autónomos, por ejemplo: robots limpiadores de pisos en fábricas, sistemas de vigilancia, transporte de partes en fábricas, recolección y cosechas de frutos entre otros. A pesar de que el estado del arte actual todavía, aún no es posible desarrollar robots complejos para que realicen estas tareas con una entera autonomía. Sin embargo sí se puede diseñar y probar prototipos y algoritmos en plataformas comerciales de amplio uso en el área científica. Como un ejemplo, se describe el robot miniatura Khepera que es una de estas plataformas con la cual se pueden diseñar y llevar a cabo una serie de experimentos relacionados con la robótica reactiva. 15 16 Capítulo 1. Conceptos básicos de inteligencia artificial y sus relaciones 1. Inteligencia Artificial “Pienso, luego, existo” son las famosas palabras del filósofo francés René Descartes1 las cuales se convirtieron en el elemento fundamental de la filosofía occidental. La interpretación más simple de esta frase es que si alguien empieza a pensar si él existe o no, este acto de pensamiento ya es una demostración que él sí existe. Sin embargo, lo que nos interesa en esta afirmación no son sus consecuencias filosóficas, sino la idea de que nuestra existencia como los seres humanos está directamente relacionada con nuestra capacidad de pensamiento. Para proceder con la discusión siguiente sobre el tema de qué es la inteligencia artificial vamos a necesitar introducir un concepto muy importante para la descripción de cualquier ciencia —el concepto del “modelo científico”. 1.1 Modelos científicos Un modelo científico es una construcción mental que representa algunas características o propiedades del objeto correspondiente. Un modelo perfecto tendría todas las características y propiedades del objeto; y en este sentido sería completamente equivalente a éste. Sin embargo, prácticamente siempre los modelos omiten o ignoran algunas características de sus objetos de 1 René Descartes (1596-1650) es el filósofo, matemático, científico e escritor francés (se pronuncia [decárt] según las reglas del francés). También tenía el seudónimo en latín Renatus Cartesius, por lo tanto el adjetivo cartesiano se refiere a las teorías o ideas relacionadas con él, por ejemplo, el sistema cartesiano de coordenadas. 17 modelado. Es completamente normal dado que los objetos son muy complejos, entonces, para poder utilizar algún modelo razonable estamos obligados a simplificar la representación del objeto hasta un cierto nivel permisible. Incluso, eso proporciona ciertos beneficios, ya que podemos ignorar las propiedades que no nos importan por el momento, y de tal manera nuestro objeto se convierte en algo más simple. A menudo diferentes modelos representan diferentes características del mismo objeto y en este sentido no se puede decir que algún modelo es mejor que el otro. Esto también se conoce como diferentes puntos de vista, es decir, si se tienen dos puntos de vista diferentes y ambos representan algunas características del objeto, de antemano no se puede afirmar que un punto de vista es correcto y otro no lo es; quizá, simplemente las características que se representan en cada punto de vista son distintas. Claro, si son exactamente las mismas características del objeto, y las conclusiones son diferentes, se puede empezar a discutir de cuál punto de vista es mejor. Por ejemplo, el tiempo se puede describir con puntos en el tiempo o con los intervalos del tiempo (véase los capítulos siguientes). Son distintos puntos de vista, ambos modelos son aplicables, y no se puede decir que uno es “incorrecto”. Sin embargo, se puede discutir sobre las ventajas de cada modelo, e incluso tratar de construir un modelo que va a combinar las ventajas de ambos. Cualquier ciencia construye modelos de su objeto de estudio, visto de manera muy general; por ejemplo, la física construye modelos de la naturaleza, la biología construye modelos de la vida (de los seres vivos), la química trata las sustancias, etc. Más adelante vamos a definir que tipo de modelos pertenecen al dominio de la inteligencia artificial. Del otro lado, nosotros como seres humanos también tenemos en nuestra cabeza un modelo específico —el modelo del mundo exterior. Éste ya no es un modelo científico, más bien es un modelode sentido común; por ejemplo, sabemos que los objetos caen hacia abajo y no hacia arriba, pero no necesariamente conocemos que este fenómeno se explica con el concepto de la gravedad, etc. Es una representación del mundo exterior que cada uno de nosotros desarrolla usando sus habilidades cognitivas e interactuando con el mundo —incluyendo la interacción con otras personas. Es decir, al percibir algo, estamos suponiendo qué cosa eso podría ser, y después actuamos en consecuencia. Si nos equivocamos, modificamos nuestra suposición y volvemos a intentar2. Así todos nosotros tenemos construido un modelo bastante completo del mundo exterior desde que éramos niños, que utilizamos en nuestra vida cotidiana. 2 Esta manera de aprender se llama aprendizaje por refuerzo, véase más adelante. 18 1.2 Búsqueda de definiciones: inteligencia El pensar es una característica muy importante de los seres humanos la que nos distingue de otros seres vivos, los que pueden reaccionar a los estímulos externos pero no pueden formular el problema y después resolverlo de manera racional, la actividad para cual usamos nuestra inteligencia natural. Entonces, nuestra inteligencia está relacionada con nuestro pensamiento. Pero ¿qué es la inteligencia? El diccionario de la Real Academia Española [3] proporciona los siguientes sentidos de la palabra “inteligencia” que nos puede interesar: 1. Capacidad de entender o comprender. 2. Capacidad de resolver problemas. 3. Conocimiento, comprensión, acto de entender. Es obvio que el sentido 3 es el resultado de utilización de de la capacidad mencionada en el sentido 1. Analicemos el sentido 1. ¿Qué significa “entender”? El mismo diccionario nos ofrece lo siguiente: 1. Tener idea clara de las cosas. 2. Saber con perfección algo. Parece que “idea clara” y “saber” es lo mismo. Consultemos la palabra “saber”, la cual se define a través de “conocer”, y si verifiquemos la definición de “conocer”, allá aparece 1. Averiguar por el ejercicio de las facultades intelectuales la naturaleza, cualidades y relaciones de las cosas. 2. Entender, advertir, saber, echar de ver. En el sentido 2 vemos un ejemplo de lo que se llama el círculo vicioso en definiciones, es decir, entender → saber, saber → conocer, y conocer → entender. (Le flecha se interpreta como “se define a través de”.) Los círculos viciosos son inevitables si el diccionario no usa un conjunto de las palabras sin definiciones (las palabras primitivas, o el vocabulario definidor), y es un fenómeno completamente normal para un diccionario escrito para los lectores humanos. Aunque en general es deseable que la longitud de los círculos sea más larga que en este caso (véase la discusión en [1], Capítulo 4). Ahora bien analicemos el sentido 1 de la palabra “conocer” (éste, a propósito, tiene su propio círculo vicioso, averiguar → inquirir → averiguar, pero eso no importa para la discusión siguiente). Y cómo ya vimos analizando el sentido 2, conocer se define a través de entender. Lo que se dice en definición 1, es que para entender un concepto debemos establecer relaciones de éste con otros conceptos; en otras palabras, incluir este concepto en nuestro modelo del mundo, y, agreguemos nosotros, sin que aparezcan las contradicciones. De hecho, el resultado de lo que acabamos de decir, tiene para 19 su descripción otra palabra importante —“conocimiento”, pues, lógico, que el resultado de conocer es el conocimiento. Resumiendo, nuestra interpretación de los conceptos “conocer” y “entender” es la siguiente: − Cada uno de nosotros tiene un modelo interno del mundo exterior construido con las experiencias previas (conocimiento). − Al encontrarnos con una experiencia nueva tratamos de ubicarla en nuestro modelo del mundo evitando las contradicciones. Y ¿qué pasa con la palabra “pensar”? El diccionario de la Real Academia Española nos da los tres sentidos siguientes: 1. Imaginar, considerar o discurrir. 2. Reflexionar, examinar con cuidado algo para formar dictamen. 3. Intentar o formar ánimo de hacer algo. De los cuales nos interesa más el sentido 2. Nótese que “formar dictamen” aquí se interpreta como “construir un modelo”. Analizando las definiciones del diccionario podemos ver que examinar → inquirir → averiguar. Acabamos de encontrarnos con la palabra “averiguar” viendo el concepto de “inteligencia”. Del otro lado, la palabra “reflexionar” no nos ayuda mucho en el análisis de “pensar” debido al círculo reflexionar → considerar → pensar. Entonces, viendo las relaciones entre las palabras, podemos concluir que “entender, conocer” es el resultado de “pensar”, mientras que “pensar” es el proceso que nos lleva a “entender, conocer”, y el resultado de “entender, conocer” es el “conocimiento”; la “inteligencia” es la capacidad de “pensar” o “entender”. El significado del concepto “entender” acabamos de ver un par de párrafos más arriba —inclusión en el modelo interno del mundo exterior sin contradicciones. Existe, sin embargo, el sentido 2 de la palabra “inteligencia”: “capacidad de resolver problemas”. ¿Es algo distinto de lo que acabamos de discutir? Creemos que no, ya que es un caso particular de “pensar”, puesto que para resolver problemas hay que pensar. Lo que se cambia en este sentido específico es que se agrega una meta u objeto de pensamiento impuesto de afuera —el problema, es decir, el problema se impone desde afuera para el acto de pensamiento. Nótese que en el sentido 2 no se incluye la pregunta de cómo encontrar los problemas para resolver. Es una pregunta también muy importante, incluso para la inteligencia artificial, sin embargo, para contestarla, es decir, para decidir qué tipos de problemas son de interés, se utiliza en una gran medida la intuición. Es más, se sabe que en una investigación científica, es mucho más difícil plantear un problema de manera correcta, que después encontrar su solución. En otras palabras, es más difícil decidir, sobre que vale la pena 20 pensar, que el propio pensar. Sin embargo, en este libro vamos a hablar de los problemas que ya están presentes y formulados, y hay que buscar una solución para ellos. 1.3 Búsqueda de definiciones: inteligencia artificial Seguimos en nuestra búsqueda de definiciones con el concepto de la “inteligencia artificial”. En el mismo diccionario de la Real Academia Española [3] podemos encontrar la siguiente definición de la IA: Desarrollo y utilización de computadoras3 con los que se intenta reproducir los procesos de la inteligencia humana. Nos parece muy acertada esta definición con las siguientes precisiones. La inteligencia artificial es una ciencia, y como cualquier ciencia ella tiene su objeto de estudio —la inteligencia humana; pero a diferencia con el punto de vista tradicional, los modelos que construye la inteligencia artificial de su objeto deben ser exactos en el sentido que fuesen “entendibles” para las computadoras. Es la diferencia entre la IA y la otra ciencia que ha estudiado la inteligencia humana durante siglos —la filosofía— pero sin la necesidad de tanta exactitud. Claro que la filosofía a parte de la inteligencia estudia muchas otras cosas. Del otro lado, la parte computacional en la inteligencia artificial es primordial —debido a la necesidad de verificación de las teorías—, por eso tradicionalmente la inteligencia artificial se considera como parte de las ciencias computacionales. Entonces, podemos reformular la definición del objeto de la inteligencia artificial de la siguiente manera: Construcción de modelos de la inteligencia humana, tales que se puede implementarlos en las computadoras. Se puede hacer una analogía con la física —antes de que se empezara a aplicar el aparato matemático en la física, ésta última era una ciencia descriptiva; después de aplicar los conceptos matemáticos, la física se convirtió en una cienciaexacta. Lo mismo sucedió con la inteligencia artificial, antes de que aparecieran las computadoras, la inteligencia artificial era parte de la filosofía —aunque no se utilizaba este nombre. Con las computadoras, la inteligencia artificial se convirtió en una ciencia exacta, ya que apareció la posibilidad de verificar sus teorías. Además, como siempre sucede con las computadoras, se agregó la posibilidad de procesar unas cantidades enormes de datos, lo que da una nueva calidad a la ciencia de la inteligencia artificial. Nótese que la palabra artificial precisamente subraya la idea de construir los 3 En la definición original, en lugar de “computadoras” se usa la palabra “ordenadores” (según el uso del español en España). 21 modelos que se pueda implementar en algún artefacto, normalmente, la computadora. Vamos a presentar algunas otras posibles definiciones de la inteligencia artificial. Cabe mencionar que cada definición representa un modelo, es decir, enfatiza algunas características e ignora otras. Una definición conocida es “sistemas basados en conocimientos”. Como ya sabemos, el conocimiento es precisamente el modelo del mundo externo, sin embargo, esa definición se centra en el conocimiento, e ignora los algoritmos que también son una parte importante de la IA. Otra posible definición es “sistemas basados en heurísticas”. Las heurísticas son las reglas o procedimientos que se aplican cuando no existe un método exacto para resolver un problema dado. Esa definición enfatiza la relación entre los métodos donde existe una solución exacta y los métodos donde no se sabe de antemano el camino a la solución, y para encontrar tal camino se usa la inteligencia, basada en el conocimiento y el razonamiento. Entre otras distinciones frecuentemente aceptadas, que se presentan, por ejemplo, en [2], las definiciones de la inteligencia artificial se agrupan en cuatro categorías, a saber, la IA se define como: − Sistemas que piensan como humanos, − Sistemas que actúan como humanos, − Sistemas que piensan racionalmente, − Sistemas que actúan racionalmente. Analizando esas definiciones, nos damos cuenta que todos se refieren a los sistemas, es decir, a los modelos implementados en las computadoras. Del otro lado, las diferencias entre las definiciones están relacionadas con el uso de las palabras “actuar” vs. “pensar” y “como humanos” vs. “racionalmente”. Nos parece que las diferencias entre ambas pares de palabras se refieren en la realidad al mismo rasgo. De hecho, tanto actuar como pensar se refieren al modelo del mundo, donde actuar implica la realización de ciertas acciones, mientras que en pensar no se realizan las acciones, pero se decide que hay que realizarlas; notemos que en actuar tampoco se realizan las acciones al azar, sino dado algunas consideraciones previas, es decir, existe algún tipo de pensamiento —sea “racional” o “como humanos”. Entonces, la única diferencia entre actuar y pensar en este caso es la implementación física de las acciones, lo que nos parece irrelevante en el contexto de análisis ya que eso no está realmente relacionado con la propia inteligencia. Ahora bien, ¿y qué significa racionalmente? Según el mismo diccionario es “relativo a la razón”, y la razón es la “facultad de discurrir”; discurrir en su turno significa “inferir, conjeturar, reflexionar, pensar, aplicar la inteligencia”. Sin embargo, nos parece que la clave de la diferencia entre “racionalmente” y “como humanos” está en las palabras “como humanos”, porque está claro que este enfoque también es racional, por lo menos todas las cosas irracionales, 22 como sentimientos, emociones, etc. que poseemos los seres humanos no son objetos de estudio de la inteligencia artificial tradicional. Es decir, las definiciones reflejan dos posibles enfoques en construcción de los modelos de la inteligencia. El enfoque que proclama “como humanos”, quiere decir que debemos estudiar los procesos cognitivos e intelectuales en los humanos y después modelar estos procesos en las computadoras, lo que significa que las computadoras deben funcionar como humanos. El otro enfoque es más pragmático, y proclama que no importa cómo es el proceso de pensamiento de los seres humanos si el resultado va a ser el mismo. El primer enfoque se llama cognitivo, mientras que el segundo tiene el nombre del enfoque de ingeniería. Un ejemplo: los aviones vuelan utilizando principios muy diferentes que las aves, —es el enfoque de ingeniería, cuando no importa como se hace en la naturaleza, pero que sí el resultado (funcionamiento). Si vamos a estudiar primero como vuelan las aves y después construir una máquina que lo haga igual, eso sería un enfoque similar al enfoque cognitivo. Existe una famosa prueba llamada “prueba de Turing4”, que consiste en que un ser humano puede interrogar a un interlocutor sin verlo, digamos, chateando, y la tarea es adivinar si es una computadora u otro ser humano. Las respuestas van a demostrar la inteligencia del interlocutor y analizándola se debe decidir si el interlocutor es una computadora o un ser humano. Obvio, para esta prueba no importa que enfoque se implemente en la computadora, lo que cuenta es solamente el resultado final; pero el desarrollador debe tomar alguna decisión referente al enfoque. Se puede criticar esta prueba con los argumentos que no se demuestra una inteligencia verdadera, sino una simulación, que no tiene nada que ver con la inteligencia de verdad. Otra parte débil de esta prueba es su antropocentrismo, es decir, no se verifica la inteligencia como tal, sino algunos rasgos específicos de los seres humanos que posiblemente no estén relacionados con la inteligencia. Sin embargo, si las preguntas se limitan a las áreas relacionadas con la inteligencia, esta prueba funcional permite entender mejor hasta dónde deben llegar los modelos computacionales para poder competir con los seres humanos. 4 Alan Turing (1912-1954) era un matemático, lógico y criptógrafo inglés que se considera el fundador de la ciencia de la computación moderna. Durante la Segunda Guerra Mundial (1939-1945) empezó a utilizar una maquina electromecánica para descifrar los códigos de comunicación naval de los alemanes nazi. Después trabajó sobre el desarrollo de una de las primeras computadoras en el mundo (Manchester Mark I). Propuso una formalización muy importante del concepto de algoritmo —la máquina de Turing (no es una computadora, es un modelo matemático formal); y además la prueba de Turing mencionada. 23 2. Estructura del área de la inteligencia artificial La inteligencia artificial está compuesta por varias áreas bastante grandes. Las diferencias entre las áreas se basan en qué parte de la inteligencia se modela. Para imaginar todo el proceso debemos evaluar como funcionamos nosotros mismos, lo que se hace con el método de la introspección —es decir, tratando de observar nuestros propios acciones, pensamientos, etc. Nuestro funcionamiento e interacción con el mundo externo consiste en: − Percepción basada en la información obtenida de nuestros sentidos — son cinco sentidos: la visión, la audición, el olfato, el gusto, el tacto; pero el sentido más importante es la visión, según algunas evaluaciones más del 90% de la información recibida es visual. − Pensamiento basado en el modelo actual del mundo, que consiste en la ubicación de las percepciones en el modelo del mundo y del razonamiento sobre este modelo para resolver problemas. − Acciones que realizamos a través de nuestro cuerpo y lenguaje. − Uso de lenguaje natural para el pensamiento y para la transmisión/recepción de información en la sociedad. Lenguaje natural es una capacidad única de los seres humanos. El lenguaje nos hace lo que somos. Ningún animal tiene un lenguaje; claro, los animales tienen sus sistemas de comunicación,pero nunca llegan a nivel de abstracción que desarrollaron los humanos. Entonces, de un lado, los humanos reciben la información a través del lenguaje y absorben toda la experiencia de la sociedad grabada en los textos y en palabras de los otros individuos. Del otro lado, el lenguaje natural es nuestra principal manera de representar el conocimiento en nuestro modelo del mundo. También podemos reaccionar no solo con las acciones físicas, sino en forma verbal entrando en un diálogo. Esta interacción determina la estructura de la inteligencia artificial como ciencia que modela la inteligencia humana, véase Ilustración 1. Esta ilustración representa el flujo de la información, con su entrada, procesamiento y salida en forma de las reacciones posibles. 24 Ilustración 1. Flujo de información en la IA. Algunos conceptos presentados en Ilustración 1 son pura información (como datos, mensajes o problemas), otros son reacciones (respuestas, acciones, resolución de problemas), el resto de los conceptos representan el núcleo de la IA como ciencia. A la percepción —que es en su gran parte la visión, los otros sentidos casi no se utilizan en la IA en su estado actual— le corresponde el área de procesamiento de imágenes y reconocimiento de patrones en imágenes. Como está claro de su nombre, dentro de esta área se modela la percepción visual y se trata de detectar e identificar los objetos en imágenes. El área de procesamiento de lenguaje natural (PLN) es una parte grande de la IA moderna. En el PLN se analizan la estructura de lenguaje humano y sus manifestaciones en los lenguajes específicos como el español, el inglés, el ruso, etc. para fines de la construcción de los modelos computacionales. También se estudian los métodos de cómo hacer que las computadoras entienden los textos, implementando análisis morfológico, sintáctico y semántico. El PLN es tan grande que a menudo se considera como una ciencia separada del área de la IA. Eso se fomenta también por el hecho que su objeto de estudio —el lenguaje natural— es fácilmente separable de los objetos de estudio de las otras áreas de la IA, como razonamiento, o representación del conocimiento, etc. Sin embargo, es necesario siempre tener en mente que el lenguaje es una parte esencial de nuestra inteligencia, aunque su procesamiento y los métodos que se usan pueden ser distintos de los métodos de las otras áreas de la IA. Las tres otras áreas —razonamiento, representación de conocimiento, aprendizaje automático— son las áreas principales de la IA tradicional. Mientras nos gustaría hacer notar la relación entre razonamiento y representación de conocimiento. El razonamiento siempre es una acción (o un procedimiento) que se realiza según ciertos algoritmos y debe realizarse sobre algo. Este algo es precisamente el conocimiento. Es decir, el conocimiento es la - Razonamiento - Representación de conocimiento (modelo del mundo) - Aprendizaje automático - Procesamiento de lenguaje natural - Percepción (visión, etc.) - Mensajes en lenguaje natural (diálogo) - Datos - Problemas - Resolución de problemas - Respuestas en lenguaje natural (diálogo) - Acciones (como en robótica o agentes) Entrada Procesamiento Reacción 25 base de razonamiento, y razonamiento son acciones sobre el conocimiento. De tal manera uno no puede existir sin el otro. Utilizando otra metáfora, se puede decir que el conocimiento es algo estático, mientras que el razonamiento es algo dinámico. El aprendizaje automático es otro tipo especial de procedimientos (algoritmos) cuando a partir de los datos puros —es decir, de algo que no está explícitamente estructurado o está estructurado solamente hasta cierto grado— se genera el conocimiento, lo que ya tiene una estructura explícita y/o más completa. Las demás áreas de la IA se pueden ser vistas o bien como una combinación de las áreas mencionadas, o como una aplicación específica en algún campo, o como la adición de algunas características específicas a las áreas mencionadas. Por ejemplo, planeación es el razonamiento en el tiempo y/o espacio, es decir, se agregan las características relacionadas con el tiempo y/o espacio. Otro ejemplo, las áreas de robótica y agentes modelan todo el proceso entrada→procesamiento→reacción. Entonces, esas áreas se pueden considerarse como una combinación de las áreas mencionadas. La diferencia principal entre esas dos áreas es la siguiente: en la robótica se supone la existencia de una máquina física (un robot) y los agentes existen como un modelo computacional (son programas). Un ejemplo de una aplicación específica es, digamos, procesamiento de la información geoespacial, donde se usan las técnicas de procesamiento de imágenes combinadas con una representación del conocimiento específico aplicado a las imágenes de la superficie terrestre o los mapas. 3. Métodos de inteligencia artificial En esta sección presentamos de manera muy general algunos métodos de la inteligencia artificial relacionados con el razonamiento y aprendizaje automático descritos a detalle en otros capítulos de este libro. Ya que el libro se centra en los métodos de la IA, es decir, en la parte de algoritmos, o en la parte dinámica, no discutiremos los problemas relacionados con la representación de conocimiento —la parte estática, estas cuestiones están descritas en otros libros, por ejemplo, en [2]. Antes que nada hay que examinar que conceptos son de mayor importancia en esta área y ver lar relaciones entre ellos. Los conceptos son: − información (datos), − aprendizaje, − clasificación, − problema, − razonamiento (enfocado en solución de problemas), 26 − optimización. Igual que en las secciones anteriores vamos a basarnos en el concepto del modelo del mundo. Además, agreguemos los conceptos intuitivamente claros: estado actual del mundo y su estado deseado. Es importante agregar que no nos ocupamos en este libro de cómo determinar qué estado es el deseado, lo consideramos como algo externo. Información son los datos que existen en el mundo. Nótese la diferencia de la información y el conocimiento: El conocimiento es la información que está incorporada en nuestro modelo del mundo. Aprendizaje es un método de cómo convertir la información en el conocimiento, es decir, es una manera de incluirla en el modelo del mundo de manera no contradictoria. Clasificación es un método de cómo llegar al saber el estado actual del modelo del mundo a partir de la información, es decir, entender, convertir la información que tenemos en el conocimiento dónde estamos en nuestro modelo. En otras palabras, basándose en la información disponible distinguir entre los posibles estados, es decir, clasificar. Un problema es un estado deseado del modelo del mundo. En este sentido razonamiento (enfocado en solución de problemas) son las acciones que hay que tomar y los cambios en el modelo del mundo que hay que realizar para alcanzar este estado deseado. Nótese que también se supone que se sabe el estado actual del mundo que se va a cambiar. Entonces, razonamiento son las acciones que nos llevan al cambio del estado actual al estado deseado. Optimización es un método que nos lleva a base de lo que se sabe del estado actual al saber el estado deseado del mundo. Es decir, mi estado actual puede ser no es el mejor, pero a partir de ese estado, puedo alcanzar un estado mejor (optimizado). A diferencia de solución de problemas, no se dicen las acciones que hay que tomar. Sin embargo, está claro que ése puede ser un paso trivial cuando la acción es “cambiarse al estado óptimo”, —en este caso la optimización va a ser equivalente a la solución de problemas. Entre los conceptos mencionados —aprendizaje, clasificación, razonamiento, solución de problemas, optimización— son los conceptos que corresponden a los métodos de la inteligencia artificial. Todos esos métodos tienensu representación en este libro. Referencias [1] Alexander Gelbukh, Grigori Sidorov. Procesamiento automático del español con enfoque en recursos léxicos grandes. IPN, 2006, 240 p. http://www.gelbukh.com/libro-procesamiento/ [2] Stuart Russel, Peter Norwig. Inteligencia Artificial. Enfoque moderno. Prentice Hall, 1996, 979 p. 27 [3] Diccionario de la Real Academia Española. www.rae.es. Consultado 30.04.2008. [4] Nils Nilsson. Problem-solving methods in artificial intelligence. NY, McGrow-Hill, 1971, 255 p. [5] Elaine Rich, Kevin Knight. Artificial Intelligence. NY, McGrow-Hill, 1990, 621 p. 28 Capítulo 2. Búsqueda heurística 1. Introducción La teoría de búsqueda heurística es un área clásica y bien desarrollada de la Inteligencia Artificial, que sigue manteniendo su actualidad dado su aplicación en los problemas prácticos. Dos elementos fundamentales de resolución de problemas dentro de esta teoría son: representación del problema (formalización) y la propia resolución —búsqueda. En este capítulo, se presentan dos enfoques para la resolución de problemas, y de modo correspondiente, dos maneras de su representación: − Enfoque basado en el uso del espacio de estados, y − Enfoque basado en la reducción de problemas. Para ambos enfoques se presentan los algoritmos para la búsqueda de soluciones. Una propiedad importante de la gran mayoría de esos algoritmos es el uso de la información heurística. Heurística es cualquier regla, estrategia o procedimiento que ayuda sustancialmente en la resolución de algún problema. Dentro del área de la Inteligencia Artificial y de la teoría de búsqueda, la información heurística es todo relacionado con el problema específico en cuestión y sirve para su solución más eficaz. En este capítulo también presentamos los procedimientos básicos de búsqueda en los árboles de juegos, que se usan aplicando a los juegos el enfoque basado en reducción de los problemas. Ésos procedimientos actualmente se utilizan en programación de un espectro bastante amplio de juegos —juegos de dos participantes con la información completa. Igual que en muchos otros libros dedicados a la Inteligencia Artificial, los conceptos principales y los métodos de la búsqueda heurística se explican usando como ejemplos los juegos, rompecabezas, y los problemas matemáticos famosos. Esa tradición que se sostiene por más de 30 años de existencia de la 29 teoría de búsqueda heurística tiene una razón importante. Como dice uno de los creadores de esta teoría N. Nilson (1971): “los juegos y problemas matemáticos no se usan porque son claros y simples, sino porque representan mayor complejidad con una estructura mínima… en los problemas relacionados con juegos y rompecabezas aparecieron y se pulieron muchas ideas que resultaron ser realmente útiles para los problemas realmente serios”. 2. Búsqueda en el espacio de estados 2.1 Representación de los problemas en un espacio de estados Un típico representante de una clase de problemas para los cuales es aplicable la representación con espacios de estados es un rompecabezas conocido como el juego de “quince”, véase Ilustración 1a. En este rompecabezas se usan quince fichas numeradas de 1 a 15. Las fichas se encuentran dentro de un cuadrado 4x4. Una celda de este cuadrado siempre se queda vacía, de manera que una de las fichas vecinas puede moverse —vertical o horizontalmente— para ocupar este espacio vacío y dejando como vacío su posición anterior. Una variante más simple de este juego sería el juego de “ocho” —un cuadrado 3x3 y ocho fichas— véase el ejemplo en la Ilustración 1b. En la Ilustración 1a se presentan dos configuraciones de las fichas. En este rompecabezas se requiere transformar la primera configuración —inicial— en la segunda configuración —configuración meta. Nótese que la configuración inicial se genera de manera aleatoria. La solución de este problema es una secuencia de jugadas de las fichas, por ejemplo, mover la ficha 8 arriba, mover la ficha 6 a la izquierda, etc. 11 10 2 13 7 5 1 8 3 g 14 6 12 15 4 9 1 15 14 13 9 10 5 11 6 7 g 12 8 4 3 2 ⇒ a) b) ⇒ 2 7 g 1 5 6 4 3 8 1 7 6 8 5 g 4 3 2 Ilustración 1. Juego de “quince” y juego de “ocho”. Una característica importante de este tipo de problemas (como juego de “quince” y juego de “ocho”) es el hecho que la situación inicial y la situación meta están claramente definidas. También está presente un conjunto de 30 operaciones, o jugadas, que transforman una situación a otra. Precisamente en estas jugadas consiste la solución del problema, que en teoría, se puede obtener utilizando la estrategia de prueba y error. Realmente, empezando de una situación inicial se puede construir las configuraciones correspondientes a todas las posibles jugadas, después para cada configuración obtenida construir las configuraciones que corresponden a la siguiente jugada en esta configuración, y así sucesivamente hasta obtener la configuración meta. Ahora vamos a introducir los conceptos que se usan para formalizar un problema en un espacio de estados. El concepto central es el concepto de estado. Por ejemplo, para el juego de “quince”, el estado es una configuración específica de las fichas. Entre todos los estados se distinguen un estado inicial y un estado meta. Esos dos estados juntos definen el problema que hay que resolver, véase los ejemplos en la Ilustración 1. Otro concepto importante es el concepto de operador, es decir un movimiento permitido en un estado dado. El operador transforma un estado a otro, siendo en realidad una función definida sobre el conjunto de estados y obteniendo los valores del mismo conjunto. Para los juegos de “quince” u “ocho” es conveniente definir cuatro operadores que corresponden a las jugadas de la celda vacía (fichas sin número, ficha vacía) arriba, abajo, a la izquierda y a la derecha. En algunas situaciones el operador puede ser no aplicable a algún estado: por ejemplo los operadores de jugada a la derecha y abajo no son aplicables si la celda vacía se encuentra en la esquina derecha abajo. Entonces de manera generalizada un operador es una función parcialmente definida entre los estados. En los términos de estados y operadores una solución del problema es una secuencia de operadores que transforma un estado inicial a un estado meta. La solución del problema se busca en un espacio de estados, es decir, en un conjunto de todos los estados que se puede alcanzar de un estado inicial dado utilizando operadores determinados. Por ejemplo en los juegos de “quince” u “ocho” el espacio de estados consiste en todas las configuraciones posibles de las fichas que pueden aparecer como resultado de las jugadas posibles de las fichas. Un espacio de estados se puede representar como un grafo dirigido, donde los nodos corresponden a los estados y las aristas corresponden a los operadores aplicables. Las direcciones representadas con las flechas corresponden a las jugadas posibles empezando desde el nodo al cual se aplica el operador hasta el nodo que corresponde al resultado de la jugada. Entonces, la solución del problema es un camino en este grafo que lleva desde un estado inicial a un estado meta. En la Ilustración 2 se muestra una parte de espacio de estados para el juego de “quince”. Cada nodo corresponde a una configuración de las fichas que este nodo representa. Las flechas son bidireccionales dado que en este rompecabezas cada operador tiene un 31 operador inverso, o más bien, el conjunto de los operadores consiste de dos pares de los operadores mutuamente inversos: arriba-abajo, izquierda-derecha. 11 10 2 13 7 5 1 8 3 g 14 6 12 15 4 9 11 10 2 13 7 5 1 8 3 g 14 6 12 15 4 9 11 10 2 13 7 5 1 8 3 g 14 612 15 4 9 11 10 2 13 7 5 1 8 3 g 14 6 12 15 4 9 11 10 2 13 7 5 1 8 3 g 14 6 12 15 4 9 11 10 2 13 7 5 1 8 3 4 14 6 12 15 9 g 11 10 2 13 7 5 1 8 3 4 14 6 12 g 15 9 11 10 2 13 7 5 1 8 3 g 14 6 12 15 4 9 Ilustración 2. Una parte de espacio de estados para el juego de “quince”. Los espacios de estados pueden ser muy grandes y hasta infinitos, pero en todos los casos se supone que el conjunto de los espacios de estados es enumerable. Entonces, en el enfoque de solución de los problemas utilizando un espacio de estados el problema se le presenta como una tupla (Ei, O, Em), donde: Ei es un estado inicial, O es un conjunto finito de los operadores que son aplicables a no más que enumerable conjunto de estados Em es un estado meta. El siguiente paso en la formalización de un problema supone la selección de algún modo de descripción de los estados del problema. Para eso se puede utilizar cualquier estructura aplicable de los lenguajes de programación 32 estándar: cadenas, listas, arreglos, árboles, etc. Por ejemplo, para los juegos de “quince” u “ocho” la estructura más natural para la representación de un estado es un arreglo bidimensional. Es importante mencionar, que de la selección de modo de representación de un estado depende la manera de la descripción de los operadores del problema, los que también deben ser definidos durante la formalización del problema en un espacio de estados. Si vamos a utilizar algún lenguaje de programación estándar para la formalización del juego de “quince”, entonces los operadores del problema pueden ser representados como cuatro funciones de este lenguaje. Si vamos a utilizar algún lenguaje de programación basado en reglas, entonces los operadores se representan como las reglas, por ejemplo, “estado inicial → estado resultante” (Nilsson, 1980). En los ejemplos que hemos visto de los juegos de “quince” u “ocho” (Ilustración 1) cada estado meta se representa de manera directa, es decir, se conoce la posición de cada ficha en el estado meta. En los casos más complejos puede haber más de un estado meta, o bien, estado meta puede estar definido de manera indirecta, es decir, tener cierta propiedad, por ejemplo, un estado donde la sumatoria de los números de las fichas en la primera fila es menor de 10. En estos casos, la propiedad que tiene el estado meta debe ser definida de manera exacta, digamos, definiendo una función booleana que implemente la verificación de esta propiedad de un estado. Resumiendo, para la representación de un problema en un espacio de estados es necesario definir lo siguiente: − Modo de descripción de los estados del problema, incluyendo un estado inicial. − Conjunto de operadores y resultados de su aplicación a los estados. − Conjunto de estados meta o bien descripción de sus propiedades. Estas características definen de manera implícita un grafo (espacio de estados), en el cual es necesario encontrar una solución del problema. La solución del problema en un espacio de estados se realiza como una búsqueda secuencial en el espacio de estados. En el punto inicial, al estado inicial se le aplica algún operador y se construye un nuevo nodo (correspondiente a algún estado), y las aristas que lo conectan con el nodo raíz (padre). En cada paso posterior de la búsqueda, a uno de los nodos (correspondientes a estados) se les aplica un operador permitido y se construye otro nodo del grafo y las aristas correspondientes. Si el nodo construido corresponde al estado meta, el proceso se termina. 2.2 Ejemplos de los espacios de estados Vamos a ver dos ejemplos típicos de representación de problemas en un espacio de estados, que muestran que esta representación se aplica para 33 diferentes tipos de problemas. Es necesario recalcar que aunque la representación propuesta es bastante natural, no es la representación única posible, existen otras maneras de representar el problema. De manera general, la selección de representación es muy importante, ya que de eso depende la dimensión de espacio de estados y por lo tanto, la efectividad de búsqueda en él. Obviamente, la representación con espacio de estados pequeño es muy deseable, sin embargo, selección de las representaciones que disminuyen el espacio de la búsqueda normalmente requiere un análisis adicional del problema en cuestión. Consideremos la formalización en un espacio de estados del problema conocido el viajero. El viajero tiene un mapa de los caminos que interconectan a siete ciudades, véase la Ilustración 3. Él debe planear su viaje de tal manera que partiendo de la ciudad A, visitara cada uno de las otras seis ciudades B, C, D, E, F, G exactamente una vez y después se regresara a su ciudad de partida inicial. Existe otra variante más complejo del mismo problema, donde se requiere que la ruta tuviera una longitud mínima. D E B C G F A Ilustración 3. Problema del viajero: mapa de caminos entre las ciudades. El estado del problema en cuestión se puede representar como una lista de las ciudades ya visitadas por el viajero. Entonces, a los posibles estados corresponden las listas de los elementos A, B, C, D, E, F, G sin repeticiones (con la excepción de la ciudad A, que puede aparecer en la lista dos veces, en su inicio y en su final). Ejemplo de la lista que corresponde a algún estado: (A B C F). El estado inicial se define como la lista que contiene solamente el elemento A: (A). El estado meta se define como cualquier lista permitida que contenga cada uno de los elementos por lo menos una vez y que inicia y termina con el elemento A. Para los estados definidos de esta manera, los operadores del problema corresponden a las jugadas entre las ciudades, es decir, a las aristas del grafo representado en la Ilustración 3. De esta manera tenemos 13 operadores. En la Ilustración 4 se muestra un fragmento del espacio de estados resultante representado como un grafo, que también incluye la ruta que representa la 34 solución del problema. Este grafo es un árbol, es decir, al aplicar cualquier operador la lista de las ciudades ya visitadas solamente puede aumentarse, por lo tanto, al construir un nuevo nodo no podemos encontrarnos con un nodo ya procesado anteriormente. Los operadores en este problema pueden ser definidos de otra manera. Por ejemplo, para cada de las siete ciudades vamos a introducir un operador que corresponde a la jugada a esta ciudad (de cualquier otra ciudad). Este operador es aplicable a algún estado si él corresponde al mapa de los caminos y la lista que corresponde al estado actual no contenga la ciudad al cual hay que moverse. Por ejemplo, el operador de moverse a la ciudad B no es aplicable al estado (A B C D), pero sí es aplicable al estado (A D). (AD) (AG) (AE) (ABС) (ABСHDEG) (ABСHDEGA) (ABСHDE) (ABСHD) (ABСH) (AB) (A) Ilustración 4. Problema del viajero: un fragmento del espacio de estados. Ahora vamos a analizar otro problema bien conocido sobre un mono y un plátano. En un cuarto se encuentran un mono, una caja y un plátano que está colgado en el techo, tan alto que el mono puede alcanzarlo solamente parándose sobre la caja. Hay que encontrar una secuencia de acciones que permitieran al mono alcanzar el plátano. Se supone que el mono puede moverse en el cuarto, empujar la caja por el piso, subir a la caja y agarrar el plátano. 35 Claro está, que representación de los estados de este problema debe incluir los siguientes elementos: posición del mono en el cuarto, tanto horizontalmente —respecto al piso—, como verticalmente (es decir, si el mono se encuentra en el piso o se encuentra sobre la caja), posición de la caja en el piso y el hecho si el mono ya tiene el plátano o no. Todo eso se puede presentar como una lista