플래너 프로그래밍이 놀라운 이유

 (hillelwayne.com)
2P by GN⁺ | ★ favorite | 댓글 1개
  • Picat의 planner 모듈은 값 할당을 찾는 논리 프로그래밍에서 한 단계 나아가, 목표 상태까지 가는 상태 변경 시퀀스를 문제로 표현함
  • 시작 상태 Start, 전이 규칙 action(From, To, Action, Cost), 종료 조건 final(S)를 정의하면 best_plan(Start, Plan)이 최종 상태까지의 최소 비용 계획을 찾아줌
  • 격자 경로 예제에서는 이동, 경계 제한, 장애물 회피, 여러 목표 방문을 action과 final 변경만으로 다루며 목표 방문 순서도 고정하거나 자유롭게 바꿀 수 있음
  • 계획 기능은 제약 해결과 결합되어, partition problem에서 원소를 제거해 같은 합으로 나눌 수 있는 가장 큰 부분 리스트를 찾는 식의 문제도 표현 가능함
  • Picat은 연구 언어라 문서와 오류 메시지가 부족하지만, 특정 계산 문제를 빠르게 풀기 위한 도구형 언어로는 일반 언어보다 간결한 해법을 줄 수 있음

Picat과 플래너 프로그래밍의 기본 아이디어

  • Picat은 논리 프로그래밍, 명령형 프로그래밍, 제약 해결을 결합하려는 연구 언어임
  • 일반적인 명령형·함수형 프로그래밍은 입력에서 출력을 만드는 알고리듬을 작성하지만, 논리 프로그래밍과 제약 해결은 관계를 만족하는 값 할당을 찾음
  • Picat에서 소문자로 시작하는 비함수 식별자는 a, b, c 같은 atom이고, 대문자로 시작하는 식별자는 변수임
  • 아직 정의되지 않은 변수 Y가 들어간 member(Y, Arr) 같은 식에서도 Picat은 식을 참으로 만드는 값을 찾아 할당할 수 있음
    • Arr = [a, b, c, a]이면 Y는 a, b, c 중 하나가 될 수 있음
    • 이어서 X != Y 같은 조건을 넣으면 가능한 값이 더 좁아짐
    • member(a, Z)처럼 리스트 자체를 아직 모르는 상태에서도 Z를 리스트로 인스턴스화할 수 있음

계획은 값 할당이 아니라 상태 변경을 찾음

  • 계획(planning)은 방정식을 만족하는 변수 값을 찾는 대신, 특정 종료 상태에 도달하는 변수 변경 시퀀스를 찾음
  • Picat의 계획 문제에는 세 가지 요소가 필요함
    • 시작 상태 Start
    • 상태 전이를 나타내는 action 함수들
    • 상태가 종료 상태인지 판단하는 final(S)
  • Picat의 action 함수는 모두 이름이 action이어야 하며, 네 매개변수를 받음
    • 현재 상태
    • 다음 상태
    • 액션 이름
    • 비용
  • best_plan(Start, Plan)은 종료 상태까지 필요한 최단 단계 또는 최소 비용 계획을 Plan에 할당함
    • 비용을 모두 1로 두면 계획의 비용은 총 이동 단계 수가 됨
    • 어떤 길이든 상관없이 아무 계획만 필요하면 plan(Start, Plan)을 사용할 수 있음

격자 경로 찾기 예제

  • 예제 문제는 격자 위 마커가 원점 (0, 0)에서 출발해 목표 좌표에 도달하는 것임
    • 각 단계마다 상하좌우 한 칸씩 이동 가능함
    • 격자 경계 밖으로는 나갈 수 없음
    • 목표 좌표에 도착하면 성공함
  • 시작 상태는 {Origin, Goal}처럼 현재 위치와 목표를 함께 담음
    • Picat의 {a, b}는 배열 문법이며 사실상 튜플처럼 사용됨
  • final({Pos, Goal}) => Pos = Goal.처럼 패턴 매칭으로 종료 조건을 표현할 수 있음
    • 같은 내용을 패턴 매칭 없이 쓰려면 상태를 먼저 {Pos, Goal}로 분해해야 함
    • final 조건이 여러 개 있으면 그중 하나라도 참일 때 계획이 성공함
  • 이동 액션은 네 방향 {-1,0}, {1,0}, {0,-1}, {0,1} 중 하나를 선택하고, 새 좌표가 0..10 범위에 있는지 검사함
    • member({Dx, Dy}, Dir)는 가능한 방향 값을 찾는 데 사용됨
    • member(Tx, 0..10)과 member(Ty, 0..10)은 좌표가 경계 안에 있는지 검사하는 데 쓰임
    • 값을 할당하지 않는 검사 전용 predicate로는 membchk도 있음
  • 결과 계획은 {move,{1,0}}, {move,{2,0}}처럼 이동 액션과 새 좌표의 목록으로 출력됨
    • Raku 스크립트로 경로를 시각화할 수 있음
    • {Tx, Ty} != {2, 1} 같은 조건을 추가하면 특정 좌표를 피하는 장애물 회피도 가능함

여러 목표와 비용 최소화

  • 여러 목표를 방문하려면 Goal을 단일 좌표가 아니라 [{2, 2}, {3, 4}] 같은 목표 큐로 바꿈
  • 목표에 도착했을 때 목표 목록에서 해당 항목을 제거하는 새 action을 추가함
    • [Head|Tail]은 리스트를 첫 원소와 나머지로 나눔
    • Goal = [Pos|Rest]는 현재 위치 Pos가 목표 목록의 첫 항목과 같을 때만 참이 됨
    • 새 상태를 {Pos, Rest}로 두면 도달한 목표가 제거됨
  • 목표를 모두 방문했는지는 final({Pos, Goal}) => Goal = [].로 판단함
    • 현재 위치가 특정 목표와 같은지가 아니라, 목표 목록이 비었는지가 종료 조건이 됨
  • 목표를 정해진 순서대로 방문하는 방식이 항상 전체 최단 경로를 만들지는 않음
  • 목표 순서를 무시하고 전체 경로를 최소화하려면 mark 액션을 바꿈
    • Goal = [Pos|Rest] 대신 member(Pos, Goal)로 현재 위치가 목표 목록 어디든 포함되는지 검사함
    • To = {Pos, delete(Goal, Pos)}로 방문한 목표를 목록에서 제거함
    • 이 방식에서는 Picat이 다음에 갈 목표를 선택해 전체 경로 길이를 최소화할 수 있음

계획과 제약 해결의 결합

  • Picat의 계획 기능은 다른 Picat 기능과 통합되며, 계획과 제약 해결을 함께 사용할 수 있음
  • 예제로 다룬 partition problem은 숫자 리스트를 합이 같은 두 그룹으로 나누는 NP-complete 문제임
  • 이 프로그램은 숫자 리스트에서 원소를 제거해, 같은 합으로 나눌 수 있는 가장 큰 부분 리스트를 찾음
    • 입력 숫자 목록에서 원소를 제거하는 것을 계획 액션으로 둠
    • final(Numbers)는 해당 숫자 목록에 유효한 partition 해가 있는지 검사함
    • cp 모듈의 제약으로 각 원소가 왼쪽 또는 오른쪽 그룹에 들어가는지를 0..1 변수로 표현함
    • 전체 합이 한쪽 그룹 합의 두 배가 되도록 제약을 둠
  • 예제 출력에서는 [5,17]을 제거한 뒤 남은 리스트를 두 그룹으로 나눠 각각 합 1108을 만들 수 있음
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • 이 방식은 유효한 제약을 직접 푸는 데서 그치지 않고, 유효한 제약 상태에 도달하기 위한 변경까지 계획으로 표현함

Picat을 쓸 때의 한계와 적합한 용도

  • Picat은 연구 언어라 프로덕션 사용에는 권장되지 않음
  • 편의 기능이 많지 않고, 좋은 문서나 명확한 오류 메시지도 부족함
    • 해결 가능한 계획이 없을 때 오류는 *** error(failed,main/0)처럼 출력됨
  • Windows에서 실행 가능하다는 점은 많은 연구 언어보다 낫다고 평가됨
  • Picat은 유지보수하거나 공유할 코드를 작성하는 언어라기보다, 특정 종류의 계산 문제를 풀기 위한 툴킷 언어에 가까움
  • 일반 프로그래밍 언어와 제약 해결기로 처리하기 어려웠던 일부 문제를 Picat으로는 꽤 우아하게 풀 수 있음

다른 계획 언어와 관련 개념

  • 계획은 원래 로보틱스와 AI에서 개척됐지만, 현재는 비디오 게임 AI에서 Goal Oriented Action Planning(GOAP) 이라는 이름으로 자주 쓰임
  • PDDL은 독립 플래너가 입력으로 받는 계획 서술 언어임
    • SAT에서 DIMACS가 서술 형식으로 쓰이는 것과 비슷한 역할을 함

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Picat의 계획 모드를 실제 업무에서 써봤음
    여러 장비 묶음의 유지보수를 조율하는 시스템을 프로토타입으로 만들었고, “어떻게 할지”가 아니라 “무엇을 원하는지”, “가능한 행동은 무엇인지”, “지켜야 할 제약은 무엇인지”를 입력하는 방식이었음
    작은 예제에서는 최적 계획을 잘 만들었지만, 실제 규모로 커지자 예상대로 무너졌고, 계획 문제는 결국 EXPTIME이라서 한계가 컸음
    Picat에는 휴리스틱을 정의하는 탈출구가 있어서 상태 술어의 랜덤 포레스트와 나이브 베이즈 분류기로 유망한 경로를 예측하게 했지만, 대칭 깨기 제약과 계층적 계획까지 넣어도 손이 너무 많이 갔음
    고전적 GOFAI 문제 영역에는 아직 AI 겨울이 남아 있는 듯함
    계획 문제를 “잠재적으로 지수적으로 긴 계획을 생성하는 다항 시간 생성기”를 반환하도록 재정식화하면 아닐 수도 있음

    • 상용 해법기는 오픈소스보다 성능도 훨씬 좋고 지갑도 훨씬 빨리 비우게 만듦
      CPLEX, Xpress, GUROBI, Hexaly가 떠오르고, Hexaly는 일정 계획이나 차량 경로 문제에 특히 좋음
      보통 업계에서 많이 쓰는 언어용 API로 접근하는데, 범용 작업에 약한 전용 해법기 언어보다 이 방식이 훨씬 말이 된다고 봄
      Python에서 GUROBI를 호출하는 건 매우 쉽고, Python의 일반 기능도 그대로 쓸 수 있음
      Mosek은 GUROBI보다 훨씬 싸지만 API가 둘 다 매우 저수준이고 성능도 GUROBI만 못함
    • 이 경우에는 CP-SAT(https://developers.google.com/optimization/cp) 같은 것이 잘 확장됐을 가능성이 있음
      이 해법기는 말도 안 되게 많은 변수와 제약을 쉽게 처리하고, 내장 휴리스틱도 훌륭함
    • 예전 계획기는 어떤 규칙을 적용할지 정하는 메타 규칙이나 휴리스틱을 포함해 탐색 공간을 줄였음
      어떤 시스템은 문제를 서로 다른 표현으로 나누고, 특화된 자동 해법기를 붙였음
      Jahob Analysis System과 Cyc가 떠오름
      실제 사용 측면에서 고전 AI에서 가장 깔끔했던 설계는 Procedural Reasoning System이었고, 약점을 현대적 방법으로 보완해 다시 만든 버전을 한번 보고 싶음
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • 왜 고품질 오픈소스 해법기가 없을까 궁금함
      다른 수치 계산 분야에서는 최신 기술이 오픈소스인 경우가 많은데, 최적화 분야만 왜 다른지 늘 의문이었음
    • 결과나 성능 면에서 보면, Prolog를 어렴풋이 떠올리며 대충 짠 깊이 우선 탐색과 실제로 크게 다르지 않은 것 아닌가 싶음

  • 제약 프로그래밍 커뮤니티에서 활발한 HN 사용자 hakank, 즉 Hakan Kjellerstrand가 Picat 자료와 예제를 많이 모아둔 사이트가 있음: http://www.hakank.org/picat/

  • 평소처럼 Prolog를 추천하고 싶음
    우아하고 이해하기 쉬우며 더 성숙했고, 유한 영역 제약 해결을 원하면 기본 구성만으로도 충분함
    그 밖에 MiniZinc는 다양한 목적에 특화된 여러 해법기에 접근하는 훌륭한 인터페이스라서, 전문가가 아니라면 원하는 결과에 더 가까이 갈 가능성이 큼
    Prolog는 장점이 많지만, 좋은 성능을 내려면 필요한 “기계적 감각”이 금방 상당해질 수 있음
    Picat으로 무언가를 작성했다면, 같은 걸 다른 언어로 어떻게 쓸지도 생각해보면 좋겠음
    이런 장난감 문제는 다른 언어에서도 쉽고, 대부분의 함수형 언어에서 Dijkstra나 A*는 몇 줄이면 되며, 결국 탐색 알고리즘의 상태 공간을 정의하는 일이 전부인 경우가 많음

  • 리뷰어로 Predrag가 보여서 반가웠지만 동시에 전혀 놀랍지 않았음
    Firebase technical screen은 이런 도구가 있었으면 훨씬 쉬웠을 것 같고, 결국 또 하나의 최적화 문제였음
    Picat으로 다시 풀어보고 싶은 마음도 듦
    그는 프로그래밍 언어 쪽에서도 흥미로운 일을 하고 있음: https://github.com/obi1kenobi/trustfall

  • 처음 든 생각은 “직접 풀어야 하는 타입 시스템 같네”였음
    TypeScript로 순진하게 표현하려 해봤지만, a, b, c가 모두 같을 수 있어서 아무것도 해결되지 않았음
    올바르게 표현하려다 보니 어느 정도 쓸 수 있어 보이는 형태까지는 갔지만, 여전히 단언을 쓰고 Y의 타입도 제대로 표현하지 못함
    이 과정이 오히려 계획기 스타일 프로그램이 단순성과 간결성 면에서 얼마나 강력한지 보여줌
    TypeScript는 이런 종류의 제약을 표현할 만큼 강력하지 않은 것 같음
    실험한 TS Playground 링크: http://tinyurl.com/3p2pzdtn

  • GOAP가 다시 언급되는 걸 보니 좋음
    F.E.A.R.의 적들이 그렇게 재미있었던 비밀 소스였고, Jeff Orkin의 작동 방식 논문도 읽기 쉽고 재미있음

  • Prolog와 일부 CLPFD를 실제 업무에서 쓰고 있는데 정말 좋음
    어디에나 있었으면 좋겠고, 더 정확히는 순수성을 강조하는 논리 핵심을 두고 명령형 동작은 가장자리로 밀어내고 싶음
    업계가 이렇게 나쁜 도구들에 갇혀 있는 것 같아 안타까움

  • Prolog와 비슷해 보이고 흥미로움

  • 이런 프로그래밍 방식 자체가 완전히 새롭진 않음
    대학에서 Prolog를 배웠고 꽤 비슷해 보이지만, Prolog에는 계획기 기능이 없었음
    다만 계획기는 문제를 푸는 매우 우아하고 단순한 방식임
    글 끝의 비디오게임 관련 부분을 보니 궁금해짐
    계획기 기능은 몇 줄의 명확한 코드로 문제를 아주 쉽게 풀게 해주지만, 명령형으로 작성한 알고리즘과 비교하면 성능이 어떨까?
    Picat은 비슷한 언어들과 비교하면 꽤 효율적인 듯하지만 [1], “표준” 언어와의 비교는 찾지 못했음
    [1]: https://arxiv.org/abs/1405.2538

  • 컴퓨터에게 도달해야 할 상태만 말해주는 꿈은 나에게도 있음
    계획 커뮤니티나 해법기는 잘 모르고 ortools를 순진하게 만져본 정도지만, **A***로 한 상태에서 목표 상태로 가는 코드 생성을 해본 적이 있음
    상태 사이를 이동하기 위한 어셈블리 명령을 생성하고, 함수 호출의 숨은 상태 전이까지 찾아 목표에 도달함
    탐색 속도를 높이기 위해 Python multiprocessing으로 병렬 실행도 했고, 스레드마다 이웃 생성이 달라서 동적 이웃 생성을 사용했음
    원래 시도에서는 A*를 병렬화하기 어려워 샤딩이 필요했음
    내 실험의 꿈은 컴퓨터에게 “지금 가진 것”과 “원하는 것”을 알려주면 올바른 이동 경로를 스스로 찾아내는 것임
    개인적으로 프로그래밍은 Factorio나 공장 같은 물류에 가깝다고 봄
    그래서 “sliding puzzle”이라고 부르는데, 올바른 그림을 보기 위해 물건을 이리저리 옮겨야 하는 퍼즐이기 때문임
    GitHub 저장소와 메모: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3

답변달기